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

백트래킹으로 푸는 문제인데, 나는 일단 백트래킹이 무엇인지 몰라, 아는 방식으로 풀었다:

from itertools import permutations
import sys

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

list_N = [str(x) for x in list(range(1, N+1))]

for j in permutations(list_N, M):
    print(' '.join(j))

나는 itertools에서 permutations함수를 불러와서 간단하게 풀 수 있었다.

백트래킹 풀이

백트래킹 풀이를 한번 살펴보도록 하겠다. 이는 나도 공부하면서 내가 작성한 코드이다:

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):
        # 만약 해당 값이 True이면, 건너뛰고 다음 loop로 넘어간다.
        if check_list[i]:
            continue
        # 자기 자신은 True라는 값으로 지정해준다.
        check_list[i] = True
        output.append(i+1)
        # 현재 i번째를 기준으로 새로운 가지를 하나 더 만들어주는 작업이다.
        dfs(depth+1, N, M)
        # 여기서 가지의 끝 부분이 끝나면 되돌아가면서 실행이 된다.
        output.pop()
        check_list[i] = False

dfs(0, N, M)

여기서 사용하는 원리는 DFS로, Depth-First-Search의 의미를 가지고 있다. 그래프의 한 뿌리, 한 뿌리 개별로 하나씩 일일이 검사해주는 방식이다. 이는 사실 이해하기 너무나도 힘들었던 탐색 방법이다. 개념은 이해했으나, 코드로는 이해를 하기가 매우 힘들었다. 다음에 이에 대해 매우 자세하게 다루어보도록 하겠다.