15649. N과 M(1)

백트래킹 단계를 시작하면서, 이게 무엇인지부터 찾아봤다.

완전 탐색의 일종인데, 완전 탐색은 모든 경우를 다 살펴보지만

백트래킹의 경우 그게 아니라면 쳐내고 살펴본다고 한다.

DFS, BFS가 그 예시라고 함.

 

나같은 경우 직접 순열을 DFS로 코딩해본 적이 없어서 기본기를 잡느라 오래 걸렸던 문제였다.

DFS가 무엇인지 알고, 스택을 사용한다는 것도 알고 있었는데 직접 내 손으로 만들어보려니 생각이 나질 않았다.

많이 쓰이는 알고리즘이라고 하니 한 번 이해하고 스택 구현하듯이 외울 정도가 되어도 나쁘지 않을 것 같다.

 

n, m = map(int, input().split())
lst = []
for i in range(1, n+1):
    lst.append(i)
check = [False] * n
tmp = []

def Print(string):
    for num in string:
        print(num, end=' ')
    print("")

def dfs(cnt):
    if cnt == m:
        Print(tmp)
        return
    for i, v in enumerate(check):
        if v == True:
            continue
        check[i] = True
        tmp.append(lst[i])
        dfs(cnt+1)
        tmp.pop()
        check[i] = False

dfs(0)

 

자세한 설명은 밑에 참고한 블로그에 써 있긴 하지만, 정리할 겸 내 언어로 풀어가보면 이렇다.

코드를 실행하면 마지막 줄의 dfs(0)부터 시작되는데 맨 처음에 인덱스 0부터 탐색하겠다는 뜻이다.

15649번 문제를 보면 '오름차순'으로 정렬하라고 했기 때문이다. 리스트를 오름차순으로 정렬해놨기 때문에...

 

dfs 함수에 처음 들어가게 되면, 14번줄 cnt가 m인지 묻는 것은 나중을 위한 것이다. 

일단 17번째 줄을 보게 되면 check 리스트를 순회하는 것을 볼 수 있다.

check 리스트는 False로 초기화되어있는데,

처음에는 True인 것이 아무것도 없으므로 일단 check[0]을 True로 만들고 (=순열로 선택하고)

같은 인덱스를 가진 리스트의 원소를 tmp 리스트에 추가시킨다. (21 line)

중요한 것은 22번째 줄 dfs 함수를 재귀호출하는 것에 있는 듯 하다.

아까 말했듯 14번째 줄에 m개만큼 선택을 전부 다 했는지 묻고, 그렇다면 프린트를 한다.

이후에 재귀를 벗어나 15번째 줄로 돌아오게 되는데, 선택했던 것을 다시 빼내고 check도 False로 바꾼다.

이러한 아이디어다.

 

중간에 실수했던 점은 tmp.pop()을 재귀함수 밑이 아닌 프린트 함수 내에 썼던 것인데,

프린트를 한다=출력을 한번 했으니까 그 다음엔 빼내야지. 라고 단순하게 생각했기 때문이다.

저 생각이 틀린 것은 아닌데, 문제는 pop의 위치이다.

프린트할 때만 pop을 하니까 

1 2

1 3 

1 4

1 5 

1 2 3

1 2 4

...

이런 식으로 출력이 되었다. 1, 5 -> 1, 2, 3으로 넘어갈 때 5만 pop하고 그 다음 넣을 원소를 찾게 됐던 것.

14번째 줄의 cnt == m 일 때만 pop을 했던 것이다.

1, 5에서 5를 빼낸 후 리스트에 1만 남아있을 때 다시 재귀 복귀를 해서 또 pop이 이루어져서 1도 빼내야 하는데 말이다.

 

말로 하니까 어려운데...그랬다.

 

 

 

https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

를 참고했다.