"백트래킹은 영리하게 무차별하는 법이야: 선택하고, 어디로 가는지 탐색하고, 벽에 부딪히는 순간, 취소하고 다음을 시도. 막다른 길에서 걸어 나오는 걸 기억하는 미로 주자야."
선택 공간을 통한 DFS
많은 문제가 선택의 연속으로 해법을 짓길 요구해: 이 순열에 다음 어느 수, 이 열에 어느 퀸, 이 스도쿠 칸에 어느 숫자. 백트래킹이 그 부분 해법 공간을 깊이 우선으로 탐색해 (Graphs 트랙의 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) 그다음 건너뛰기 선택 (그냥 재귀) — 8 리프. N-퀸 가지치기: 퀸이 기존 거랑 충돌하는 순간, 그 놓기 건너뛰고 재귀 안 해 — 그 아래 배치 서브트리 전체를 잘라, 완전한 보드 짓고 끝에 거부하는 대신.
Progress
Progress is local-only — sign in to sync across devices.