#15649

정현이 형이 백트래킹에 대해서 공부를 간단하게 해보고 N과 M 문제를 풀어보라고 추천해줬다. 처음에 접근하기는 어려우니 정답을 보고 그 코드 자체를 이해해보려고 해라!! 라고 했다. 하지만 그건 자존심이 허락하지 않는다. 그래도 부산대 컴공 4학년 아닌가 비록 알고리즘을 시작한지 얼마 되지 않았다지만 정답을 보고 정답을 이해하라니 절대 그럴 수 없다.

코드를 바로 짜기 시작했다. 이면지에 대고 줄줄 써보기도 하고 생각도 오래 했다.

결론은 DFS 였다. 핵심은 어디서 pop을 해줄 것이며, 어디서 dfs를 들어갈건가 였다.

그렇다. 풀지 못했고, 도움을 받았다. 하지만 이 문제와 다음 문제(15650번 - N과 M (2))은 확실하게 완벽하게 이보다 더 잘 이해할 수는 없을 정도로 내 걸로 만들었다. 그 과정을 적어보려고 한다.

생각의 흐름

큰 틀은 잡았으나, 어디서 pop 을 해줘야 하는지가 계속 헷갈렸다. 정현이 형의 도움을 받았고, 이 문제에만 적용하는 것이 아니라

백트래킹의 전체적인 개요, 폼, 흐름을 이해하고자 노력했다. (행님이 모자란 돌멩이 이해 시킨다고 애를 좀 먹었지 싶다.. 재귀의 흐름-스택 부분을 설명해줄 땐 꽤 답답해하는 눈치였다^^)

정답 코드

N, M = map(int, input().split())

numList = []

def dfs():
    if len(numList) == M:
        for a in numList:
            print(a,'', end='')
        print()
        return

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

이게 뭐라고.. 이렇게 간단 명료한 걸...

for 문 안에 if 구문, append, dfs, pop 의 위치가 어디냐에 따라 결과는 천차만별이다.

일단은 내가 이해한 대로 나만의 방식대로 여기에 기록해둘 것이다. 나중에 더 쉽게? 설명할 수 있는 레벨이 된다면 다시 수정해보자.

dfs를 처음 실행하면 빈 배열부터 시작한다. 차례대로 for 문을 돌면서 배열(numList)에다가 숫자를 집어넣는다.

근데 여기서 if문(개수가 2개->M 가 되면 출력하기)이 왜 for문 보다 먼저 나오는가?

사실 이것만이 정답이 되는 건 아니다. 하지만 이걸 앞으로의 백트래킹 문제들에서 적용할 나만의 정형화된 틀? 폼? 이라고 생각하려고 한다.

숫자를 집어넣거나 빼거나 하기 전에 내가 최종적으로 하고 싶은 작업 ( 이 문제에서는 배열의 길이가 2가 되면 숫자 출력 )의 조건을 판별하고 먼저 해당 작업을 수행한다.

자 이제 백트래킹의 핵심, dfs 내부의 for문을 보자.

먼저 배열 안에 해당 숫자(i)가 있는지 확인하고 없으면? i를 추가한다(append). 그리고나서? dfs를 다시 호출(dfs 실행)해주고 언제가 될 지 모르지만 아무튼 그게 끝나면?(호출했던 dfs return) 그 다음에 마지막 숫자를 꺼내준다 (pop) 이러한 로직,코드,순서가 나온 이유를 내가 이해한대로 설명해보자면,

입력이 4 2 로 주어진 상황, 제일 처음 i 가 만약 1 임을 가정.
(재귀를 따라가며 백트래킹을 이해해보자)

1. 제일 처음 dfs 실행
2. if 문 걸러지고 -> 빈 배열이므로
3. for 문 시작
4. i = 1
5. 배열에 아무것도 없으므로 1 append
6. dfs 호출

내가 이해한 방식은 이 때의 dfs(6번)를 "1이 실행한 작업"이라고 이해하는 것이다.

작업 시작할 숫자 append -> 작업 시작 -> 작업 끝나면 -> 호출한 애를 pop

이게 백트래킹의 핵심이라고 이해했다. 다시 흐름으로 돌아가면

7. 새로 들어온 dfs에서 배열의 길이는 1( numList = [1] )이므로 if 제끼고
8. for 문 다시 시작
9. i = 1
10. 이미 배열에 1이 있으므로 i = 2
11. 2는 배열에 없으므로 2 append
12. dfs 호출
13. 배열의 길이가 2 이므로 print 해주고 return

자 여기서 어디로 돌아가냐? 바로 10번으로 간다.
i가 2일 때 호출했던 dfs가 끝났고 pop을 해준다. 그럼? 위에서 말한대로 작업 시작할 숫자 (2) 를 append, 작업 시작, 작업이 끝났으므로 pop, 그럼 다시 정상적으로 for문을 돌고

14. i = 3 (작업 시작할 숫자) append, dfs 호출, print, pop
15. i = 4 가 되고 14번과 같이 수행

자 여기서 i = 4까지 하고나면 for문이 끝난다. (return이 아님)
그럼 어디로 가냐? 바로 6번으로 간다. i가 1일 때 dfs를 호출했고 그게 끝난 것이다. (작업할 숫자 = 1, 작업이 끝난 상황) 그럼 작업을 호출했던 숫자를 pop 해주면 된다.

16. numList = []

다시 제일 처음 for문으로 돌아가서 정상적인 흐름을 탄다. => 4번
i는 2가 되고 5번 부터 다시 똑같은 과정을 수행한다.

print를 찍어가면서 배열을 확인하고 재귀의 흐름을 따라가면 훨씬 이해가 쉬울 것이다. (나는 종이에 적으면서 흐름을 따라가는 것이 훨씬 이해하기 편했다)

전형적인 백트래킹 문제의 아주 기본 중의 기본 중의 기본이라고 한다. 여기서 조금씩 응용을 하면 된다. 첫 발을 잘 내딛은 것 같다. 바로 다음 문제로 넘어가보자.

핵심!!!
작업을 시작할 숫자 추가(append) -> 작업 시작 (dfs) -> 작업 끝 -> 작업을 시작했던, 호출했던 숫자 꺼내기(pop)