오늘부터는 Backtracking!

간만에 알고리즘이라 잘 풀리지가 않는다 ... 거기다가 새로운 개념이라 더더욱 ...!

1. 다른 풀이

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
s = []

def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return

    for i in range(1, n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()

dfs()

풀이 출처: https://jiwon-coding.tistory.com/21

설명을 엄청 잘 해놓으셨다!
처음에는 저 s와 pop부분이 제대로 이해가 되지 못했는데, 예시를 들어서 설명해보겠다.

만약 예시가 (4, 4)라고 했을 때

• s에 1이 없으니 s = [1]

• 이때 dfs 함수를 한 번 더 실행하여 1 딴에서 가지치기를 진행한다. 즉 두 번째 dfs를 실행하는 것이다. (dfs에 dfs가 있는 상태)

• 이때 1은 이미 s에 있으므로 2,3,4를 추가해줄 수 있다. 2를 추가했으면 거기서 또 가지치기를 하여 세번째 dfs가 실행이 된다. (dfs에 dfs에 dfs가 있는 상태)

• 1,2는 이미 s에 있는 상태이므로 3과 4만을 추가할 수 있고 또 3 딴에서 가지치기를 진행한다. (dfs, dfs, dfs에 dfs가 또 생긴 상태)

• 그 후에는 1,2,3이 이미 s에 있으므로 4만을 추가할 수 있고 이를 통해 첫 번 째 답인 1,2,3,4가 출력되게 되는 것이다.

• 이 다음으로는 각각의 dfs의 다음 코드가 s.pop이므로 하나의 dfs씩 뒤로 가며 새로운 가지치기를 진행한다.

이를 그림으로 나타내면 아래와 같다.

두 번째 dfs에서의 3, 세번째 dfs에서의 4에서 가지가 뻗어나온 것처럼 보이지만 자리가 없어서 ^^... 각각 2, 3에서 뻗어나온 가지이다.

2. 마치며

풀이를 봐도 가지치기 ? 으잉? 이랬는데 ... 그림을 그려서 이해해보니 확실하게 이해가 됐다. 이해가 안되면 그림으로 표현해보자!