"백트래킹은 무차별 대입을 영리하게 하는 방법이야. 하나 고르고, 그게 어디로 가는지 탐색하고, 벽에 부딪히는 순간 취소하고 다음 걸 시도해. 막다른 길에서 걸어 나오는 법을 기억하는 미로 주자인 셈이지."
선택의 공간을 훑는 DFS
많은 문제가 선택을 이어 붙여 해법을 짓기를 요구해. 이 순열의 다음 자리에 어떤 수를 놓을지, 이 열에 퀸을 어디 둘지, 이 스도쿠 칸에 어떤 숫자를 넣을지. 백트래킹은 그 부분 해법의 공간을 깊이 우선으로 훑어. 그래프 트랙의 DFS를 암묵적인 결정 트리 위에서 돌리는 셈이지. 템플릿은 세 박자야. 선택지 하나를 고르고, 그 결과를 보러 재귀하고, 그다음 선택을 취소해서 다음 선택지를 시도해. 그 취소가 바로 백트랙이고, 코드 하나로 모든 가지를 서로 오염시키지 않고 탐색하게 해주는 장치야.
선택하고, 탐색하고, 취소하는 템플릿
거의 모든 백트래킹 해법이 같은 골격을 가져. 지금의 부분 해법이 완성됐으면 기록하고, 아니면 가능한 선택지를 돌면서 하나씩 적용하고, 재귀하고, 되돌려. 입문자가 잊는 건 언제나 되돌리는 단계고, 그걸 잊으면 앞선 선택이 뒤쪽 가지로 새어 나가. 선택하고 재귀하고 선택 취소하는 이 리듬이 손에 붙으면 장르 하나가 통째로 열려. 순열, 부분집합, 조합, N-퀸, 스도쿠, 미로 풀기, 단어 검색, 유효한 괄호 생성까지.
백트래킹은 선택 트리 위를 훑는 DFS야. 선택지를 고르고, 탐색하러 재귀하고, 다음 걸 시도하려고 선택을 취소해. 그 취소가 백트랙이고. 전부 뒤지는 탐색 공간은 지수적이니까, 가망 없는 가지를 일찍 버리는 가지치기가 이걸 감당 가능하게 만들어.
가지치기: 감당 가능함과 절망 사이의 차이
결정의 공간은 보통 지수야. 순열이 n!개, 부분집합이 2ⁿ개니까 순진하게 전부 뒤지는 건 규모가 커지면 가망이 없어. 백트래킹을 살리는 게 가지치기야. 어떤 가지가 가망 없다는 게 증명되는 순간 그 가지를 통째로 버리는 거지. 끝까지 탐색해 보고 버리는 게 아니라. N-퀸에서 퀸을 놓자마자 충돌이 생기면 그 가지로는 아예 재귀를 안 해. 그 아래 서브트리 전체가 잘려 나가는 거야. 가지치기를 잘하면 천문학적인 탐색이 밀리초 만에 끝나기도 해. 백트래킹의 기술은 선택하고 취소하는 메커니즘이 아니야. 그건 기계적이니까. '이 가지는 안 되겠다'고 말할 수 있는 가장 이른 순간을 찾아내서 거기서 자르는 거지.
피파의 고백
내가 처음 짠 순열 생성기는 쓰레기를 뱉었어. 결과마다 앞 결과의 찌꺼기가 묻어 있더라고. 아빠가 바로 짚었어. 선택하고 재귀는 했는데 선택 취소를 빠뜨렸다고. 내가 쌓아 올리던 경로가 가지 사이에서 한 번도 청소되지 않았던 거야. 취소 한 줄을 넣으니 전부 고쳐졌지. 그리고 더 깊은 교훈은 N-퀸에서 왔어. 내 버전은 답은 맞는데 느렸고, 이유는 충돌을 마지막에 확인했기 때문이었어. 퀸을 놓는 도중에 가지치기를 하도록 바꾸니 타임아웃이 즉답으로 바뀌더라. 실패를 감지한다는 사실만큼이나 언제 감지하느냐가 중요하다는 걸 백트래킹이 가르쳐 준 거야.
Code
순열 만들기: 선택하고, 탐색하고, 취소하고·python
# 백트래킹으로 모든 순열: 선택 / 재귀 / 선택취소.
def permutations(items):
result = []
path = []
used = [False] * len(items)
def backtrack():
if len(path) == len(items): # 완성된 해법 -> 기록
result.append(path[:]) # 복사! path 가 계속 바뀜
return
for i in range(len(items)):
if used[i]:
continue # 가지치기: 원소 재사용 불가
path.append(items[i]); used[i] = True # 선택
backtrack() # 탐색
path.pop(); used[i] = False # 선택취소 (백트랙!)
backtrack()
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
# path.pop() + used[i]=False 가 취소야. 잊으면 앞 선택이 뒤 가지로 새
# -> 틀린 답. N-퀸은 가지치기 추가: 충돌하는 놓기는 건너뛰어,
# 탐색하기 전에 서브트리 전체를 잘라.
템플릿을 고쳐서 [1,2,3]의 모든 부분집합, 그러니까 멱집합 2³ = 8개를 생성해 봐. 원소마다 포함할지 건너뛸지 이진 선택을 하면 돼. 선택하고 재귀하고 취소하는 구조를 그려 봐. 그다음 N-퀸에서 '가지치기'가 뭘 뜻하는지, 그리고 퀸을 놓는 도중에 충돌을 확인하는 게 왜 마지막에 확인하는 것보다 나은지 설명해.
Hint
부분집합은 인덱스 i에서 items[i]를 포함하는 선택(append하고 재귀하고 pop)과 건너뛰는 선택(그냥 재귀)을 하면 리프가 여덟 개 나와. N-퀸의 가지치기는 퀸이 기존 퀸과 충돌하는 순간 그 배치를 건너뛰고 재귀하지 않는 거야. 그 아래 배치 서브트리 전체가 잘려. 완성된 보드를 다 만들어 놓고 마지막에 거부하는 것보다 훨씬 낫지.
Progress
Progress is local-only — sign in to sync across devices.