[ BOJ 오답노트 ] 15649 파이썬 : N과 M (1)

2022 02 24

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 일단 어떻게 풀지를 모르겠어서.. 틀렸다. 백트래킹 알고리즘 관련된 문제라는데 백트래킹은 아직 접해보지 못했기 때문에... 하하하

- 그래서 이번 기회로 백트래킹 알고리즘을 배워보고, 정리도 해두었다.

https://chunshikkong.tistory.com/36

[ 알고리즘 ] 7. 백트래킹 알고리즘

 

- 백트래킹은 dfs의 한 종류이기 때문에 깊이 탐색을 잘 이용해서 풀면 되는 문제였다.

- 값들을 저장할 배열 하나를 만든다.

- for문을 이용해서 해당 원소가 배열 안에 존재하는지 확인하고, 존재하지 않으면 append 해준다.

- 길이가 M과 같아졌을 때에는 return으로 dfs 함수를 빠져나온다.

 

 

 

3. 해결

n, m = map(int, input().split(' '))

arr = []


def dfs():
    if len(arr) == m:
        print(' '.join(map(str, arr)))
    else:
        for i in range(1, n+1):
            if i not in arr:
                arr.append(i)
                dfs()
                arr.pop()


dfs()

 

 

 

4. 배운 점

- 일단 나는 예를 들어서 '1 2 3 4'를 출력할 때마다 for문으로 돌려서 출력했는데, 아주 좋은 문법을 발견했다.

print(' '.join(str, arr))

- join 함수로 map 함수로 하나씩 돌아가면서 ' '와 연결해주었다.

 

- dfs 함수를 만들어서 계속해서 깊이 탐색을 하고, pop 해준 후에 다시 또 깊이 탐색을 해주는 방법을 다시 한번... 세겼다.