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

이 문제도 같이 DFS 방식을 사용하여 풀어야 했던 문제이다. 우선, 이 문제를 알기 전에 앞선 백준 15651번 포스팅을 보고 오길 바란다. 그러면 이해하기가 편할 것이다.

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
        output.append(i+1)
        dfs(depth+1, N, M)
        check_list[i] = True
        output.pop()
        for j in range(i+1, N):
            check_list[j] = False         
dfs(0,N,M)

1. 우선, 앞에 재귀를 돌려주기 전에 check_list[i]=True를 원래 지정해주었는데, 이를 이 풀이에서 지정해주지 않는 이유는, 지정해주는 순간 재귀를 돌렸을 때 처음에 지정된 숫자는 추가되지 않을 것이기 때문이다. 예를 들어, 문제에서는 1 1, 2 2 와 같이 처음에 지정된 숫자를 뒤에 추가해주길 원하는데, check_list[i]=True를 미리 지정해준다면, 1 2, 2 3와 같이 같은 숫자는 추가되지 않을 것이기 때문이다.
   
2. 이후에 마지막에는 자신을 제외한 뒤의 check_list 요소들은 False로 지정해주는데, 자신은 남겨주는 이유는, 다음 숫자로 넘어갔을 때 이전 숫자는 불러오지 않게 하기 위해서이다.