<백준 문제풀이: 15650번> 파이썬 - N과 M(2)

이번에도 백트래킹 문제였는데, itertools.permutations의 방법을 사용하지 않고 dfs 방식을 이용하느라 조금 어려웠다.

import sys

N, M = map(int, sys.stdin.readline().split())

check_list = [False]*N
output = []

def dfs(depth, N, M):
    if depth == M:
        print(' '.join([str(x) for x in output]))
        return
    for i in range(N):
        if check_list[i]:
            continue
        check_list[i] = True
        output.append(i+1)
        dfs(depth+1, N, M)
        output.pop()
        for j in range(i+1, N):
            check_list[j] = False
dfs(0, N, M)

여기서 하나씩 차근 차근 보자:

1. 우선, False가 N의 길이만큼 있는 check_list를 만들어준다. 이는 확인할 숫자인지 아닌지 분별을 해줄 역할을 하는데 사용될 것이다.
   
2. output 리스트는 출력할때 사용할 리스트이다
   
3. 일단 밑의 for문을 본다면, 만약 check_list의 i번째가 True라면, 다음 loop로 넘어간다는 것이다. 만약 아니라면, 해당 i번째는 True로 지정해주고, output 리스트에 i+1 을 추가해준다. (i=0 부터 시작하기 때문) 이후, 다시 재귀로 dfs 함수를 다시 실행한다.
   
4. 이렇게 하게 된다면, 이전에 check_list[i]=True라고 지정해놓은 부분은 건너뛰고 그 다음의 i부터 시작하게 된다. 사진을 예로 들어보겠다. 여기서는 N, M 이 각각 3, 2이다.:
   

   

5. 처음에는 i=0일 때 시작해서 output에 1을 추가한다. 그 다음, dfs(1, 3, 2)으로 넘어가게 된다. 여기서 이제 다시 i=0 일때부터 시작하게 되는데, check_list[i]=True일 경우 continue하라고 했으므로, 다음 loop로 넘어가며 i=1로 넘어가게 된다. 그래서 이 경우에는 output에 2를 추가하고, 다음 dfs(2, 3, 2)에서는 이를 출력하고 되돌아가기 시작한다.
   
6. 여기서 이제 주의할 점은, 밑에서 돌아오면서, output의 마지막 요소를 삭제해주고, 해당 요소의 뒤의 요소들은 모두 False로 지정해주는 것이다. 이는 마지막에 돌아왔을 때, 맨 앞의 자리는 True로 지정되어, 다음 loop에서 접근하지 못하게끔 하려고 하는 것이다.
   

DFS는 매우 힘들고 헷갈린다. 제대로 생각하지 못한다면 엄청나게 헷갈리고 무엇이 무엇인지 잘 모를 수가 있으니 제대로 공부하고 풀어야 할 것이다.