[Python] 백트래킹 (+ DFS와 차이)

백트래킹이란?

백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack^[각주:1] 하는 알고리즘이다. 

 

백트래킹과 DFS의 차이

처음 백트래킹을 접했을 때, 아래와 같이 생각했다.

 

그런데 공부하면 공부할 수록 아래에 더 알맞다는 걸 깨달았다.

 

백트래킹이랑 DFS(Depth First Search) 모두 탐색하는 알고리즘이라 혼동하기 쉽다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 백트래킹이랑 DFS 모두 원하는 값을 찾기 위해서 다양한 방법을 사용하는데 여기에서 차이가 발생한다. 

 

우선 백트래킹은 불필요한 탐색을 하지 않는다. 여기 a라는 배열이 있다. a는 132, 234, 123, 총 3개의 요소를 가지고 있는데, 123이라는 값을 찾고 있다고 하자. 순서대로 132라는 값에 접근했을 때, 백의 자리 수가 동일하나, 십의 자리 수가 다르기 때문에 더 이상 탐색을 진행하지 않고 다음 수로 넘어간다. 

 

그러나 DFS는 모든 경우의 수를 탐색한다. 다시 위의 예를 빌려, 132이라는 수를 탐색할 때, 십의 자리 수에 접근했을 때 원하는 수가 아님에도 불구하고 일의 자리 수까지, 즉 트리의 바닥에 도달할 때까지 탐색을 계속한다. 

 

예시

백준의 N과 M (1) 문제다.

 

간단하게 문제를 정리하자면, 자연수 N과 M이 주어지는데, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제다. 

 

N은 4이고, M은 3라는 가정 하에, 코드를 작성하기 이전 머릿속으로 한 번 어떻게 백트래킹으로 이 문제를 해결할 수 있을지 생각해보자. 

 

고려해야 할 조건은 2개다.

1. 수열의 길이가 3을 넘지 않도록.

2. 배열 내의 중복인 숫자가 있는지.

 

첫번째 요소

수열의 첫 번째 요소로는 1~4까지 모두 가능하다. 

 

수열은 사전 순으로 증가하는 순서대로 출력해야 한다니 1을 선택하자.

 

두 번째 요소

 

그럼 위의 사진고 같이 선택지가 생긴다. 사전 순대로 증가해야 하니 2를 선택하자.

 

3번째 요소

 

이제 3번째 요소까지 왔다. 수열을 구했으니 수열을 출력해주고, 다시 전 단계로 돌아가서 마지막 요소를 채우고 출력한다.

 

그럼 첫번째 요소가 1이며, 두 번째 요소가 2인 모든 수열을 만들었다. 더 이상 가능한 경우의 수는 없으니, 다시 2번째 요소를 구하는 단계로 되돌아간다. 

 

2번째 요소

이제 두번째 요소를 3으로 선택한다. 

 

3번째 요소

3번째 요소까지 모두 선택했으니 출력하고 전 단계로 돌아간다. 그다음 3번째 요소를 4로 선택한 뒤 출력한다.

이로서 1, 3, * 수열은 모두 구했다. 

 

나머지 수열들도 이와 동일한 방법으로 계속 구하면 된다. 그럼 이제 코드를 짜 보자.

 

코드

우선 이 알고리즘은 재귀의 성격을 띤다. 재귀는 탈출 조건이 필요한데, 여기에선 바로 배열의 길이가 M, 즉 3에 도달했을 때이다. 길이가 3이 되었을 때, 출력하고 전 단계로 돌아가는, return을 하는 것이다. 

 

그리고 사전 순으로 증가하는 순서로 수열을 채워야 하는데 그것은 for문으로 해결할 수 있다. 중복은 for문으로 채울 때 if문으로 그 수가 배열 내에 존재하는지 여부를 가리고, 없다면 추가, 아니라면 다음 수로 넘어가게 만들면 되는 것이다.

 

정리하면 배열의 길이가 3을 넘는지 확인하고, 넘는다면 출력 밑 return을 하고, 아니라면 배열을 순서대로 채우면 되는 것이다.

 

이걸 코드로 쓰자면 아래와 같이 된다. 

 

N, M = map(int, input().split())
ans = []

def back():
    if len(ans) == M: # 배열의 길이를 확인
        print(" ".join(map(str, ans))) # 1 2 3 이런 상태로 출력하기 위해
        return 
    for i in range(1, N+1): # 1 ~ N 까지
        if i not in ans: # 중복 확인
            ans.append(i) # 배열 추가
            back() # 재귀
            ans.pop() # return으로 돌아오면 이게 실행됨. 1, 2, 3 일때 3을 없앰으로 전 단계로 돌아가는 것
            
back()

 

번외

백트래킹으로 이 문제를 풀 수 있지만 실은 파이썬 내장 함수로 간단하게 이 문제를 해결할 수 있다. 심지어 이게 속도가 훨씬 빠르다. (메모리는 동일하지만...) 역시 파이썬! 느린 것만 빼면 최고다. 

 

from itertools import permutations
n, m = map(int, input().split())
p = permutations(range(1, n+1), m)
for i in p:
    print(" ".join(map(str, i)))

 

 

---

참고:

 

1. https://blog.encrypted.gg/945 (깔끔하게 설명되어 있으니 한 번 읽어 보는 것을 추천한다. C/C++을 몰라도 개념만 이해하면 되니 걱정하지 마시라.)

[실전 알고리즘] 0x0C강 - 백트래킹

 

2. https://gamedevlog.tistory.com/49

백트래킹(back tracking)

 

3. https://chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

 

---

 

1. 출처 - 네이버 사전 [본문으로]