백준 10974번 모든 순열(Python3)

def dfs(cnt):
    if cnt == n:
        print(*lists)
        return

    for i in range(n):
        if check[i]:
            continue
        lists.append(num_lists[i])
        check[i] = True
        dfs(cnt + 1)
        lists.pop()
        check[i] = False


n = int(input())
lists = []
num_lists = [i + 1 for i in range(n)]
check = [False] * n
dfs(0)

문제 :

해결 방법 : 백트래킹을 통해 모든 경우의 수를 탐색하여 순열을 구해주었다!

1. [] 빈 리스트에서 시작.

2. [1, ] 처음엔 check리스트가 모두 false이므로 1이 들어감.
   check = [true, flase]

3. 재귀함수를 만나 cnt = 1이 되어 재귀

4. lists = [1, 2]
   check = [true, true, false ]

5. 또 재귀. cnt = 2

6. lists = [1, 2, 3]
   check = [true, true, false ]

7. 재귀. cnt = 3
   if cnt == n에서 걸리므로
   print를 하고 return

8. return 하여 재귀함수 밑의 코드 진행.
   lists = [1, 2]
   check = [true, true, false ]

9. 이런 방식으로 쭉 반복하며 if문에 걸릴때마다 순열을 출력한다.