백트래킹 (N-Queens, 가지치기, DFS)
분할 정복·DP·그리디가 모두 효율적인 알고리즘 패러다임이었다면, 백트래킹(Backtracking)은 본질적으로 모든 가능한 답을 시도해 보는 완전 탐색의 정교한 변형이다. "일단 한 길로 가 보고, 막히면 되돌아 와 다른 길을 시도하는" 사고방식이며, N-Queens·미로 찾기·스도쿠·조합 생성처럼 답의 후보가 트리 구조로 자라는 문제에 강력하다. 핵심 기교는 가지치기(Pruning) — 명백히 답이 될 수 없는 경로를 미리 잘라 내는 일이며, 가지치기 없는 백트래킹은 단순 완전 탐색일 뿐이다. 본 글은 백트래킹의 정의·DFS와의 관계·N-Queens 고전 풀이·가지치기 전략을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms). 제가 학교 알고리즘 수업에서 처음 N-Queens 8을 단순 완전 탐색과 가지치기 버전으로 비교 측정해 본 후 시간이 100배 차이가 나는 모습을 본 후로는 "백트래킹의 90%는 가지치기"라는 인상을 손끝으로 받아들였다.
백트래킹의 정의와 DFS·완전 탐색과의 관계
백트래킹은 한 문제의 해답을 부분해(partial solution)의 트리로 표현하고, 그 트리를 DFS로 탐색하면서 더 진행할 가치가 없는 부분 트리를 잘라 내는 알고리즘 패러다임이다. 여기서 부분해란 아직 완성되지 않은 중간 단계의 답을 가리키며, 매 단계에서 한 조각씩 채워 가다가 더 못 채우면 직전 단계로 돌아가는 흐름이 백트래킹의 본질이다.
| 비교 항목 | 단순 완전 탐색 | 백트래킹 | DFS |
|---|---|---|---|
| 탐색 대상 | 모든 후보 | 유효한 후보만 | 그래프 노드 |
| 가지치기 | 없음 | 핵심 | 일반적으로 없음 |
| 되돌아가기 | 자동 (재귀 반환) | 명시적·의도적 | 재귀 반환 |
| 대표 응용 | 매우 작은 입력 | N-Queens·스도쿠 | 그래프 순회·연결 컴포넌트 |
여기서 가지치기(Pruning)란 부분해를 더 확장해 봐야 결코 유효한 해가 될 수 없음이 명백한 경로를 즉시 끊어 버리는 최적화 기법을 가리키며, 가지치기의 강도가 곧 백트래킹 알고리즘의 실용성을 결정한다. DFS와 백트래킹은 코드 구조가 거의 같지만, DFS는 그래프 자체를 순회하는 게 목적이고 백트래킹은 해 공간을 탐색하면서 가지치기로 유효 영역만 남기는 게 목적이다.
# 백트래킹 일반 골격
def backtrack(state):
if is_solution(state): # 완성된 해
record(state); return
for choice in candidates(state):
if not feasible(choice, state):
continue # 가지치기
state.add(choice)
backtrack(state)
state.remove(choice) # 되돌리기 (backtrack)이 6줄짜리 골격이 N-Queens·스도쿠·순열 생성·부분집합·미로 찾기에 모두 그대로 적용된다. 솔직히 제 경험상 학교 알고리즘 시험에서 백트래킹 문제는 거의 모두 위 6줄을 변형한 코드로 풀렸고, 한 번 외워두면 어떤 변형 문제든 자동으로 손이 움직이게 된다는 점이 가장 인상적이었다.
N-Queens 고전 풀이 — 가지치기의 위력
N-Queens는 백트래킹의 가장 고전적인 예제이다. N × N 체스판에 N개의 퀸을 서로 공격하지 않게 배치하는 문제이며, 한 행에 한 퀸씩 두므로 행 단위로 탐색하면 자연스럽게 트리 구조가 만들어진다.
# N-Queens — 백트래킹 + 가지치기
def n_queens(n):
cols = set() # 열 사용 여부
diag1 = set() # 좌상-우하 대각선 (r - c)
diag2 = set() # 좌하-우상 대각선 (r + c)
solutions = []
def backtrack(row, placement):
if row == n:
solutions.append(placement[:])
return
for c in range(n):
if c in cols or (row - c) in diag1 or (row + c) in diag2:
continue # 가지치기 (3가지 충돌 검사)
cols.add(c); diag1.add(row - c); diag2.add(row + c)
placement.append(c)
backtrack(row + 1, placement)
placement.pop() # 되돌리기
cols.remove(c); diag1.remove(row - c); diag2.remove(row + c)
backtrack(0, [])
return solutions
print(len(n_queens(8))) # 92 (8-Queens의 해 개수)
print(len(n_queens(4))) # 2핵심 가지치기 세 가지가 cols·diag1·diag2 집합 검사이다. 한 열에 이미 퀸이 있거나, 두 대각선 중 하나에 충돌이 있으면 즉시 다음 열로 건너뛴다. 이 세 줄짜리 가지치기가 8-Queens에서 시도해야 할 후보를 8^8 = 1670만에서 단 92로 줄여 준다. 여기서 두 대각선 검사 트릭이란 좌상-우하 대각선 위의 모든 칸이 행 - 열 값이 동일하고, 좌하-우상 대각선은 행 + 열 값이 동일하다는 성질을 활용해 O(1) 시간에 충돌을 검사하는 표준 기법을 가리킨다.
가지치기 없는 단순 완전 탐색과 비교하면 차이가 명확하다.
| 방식 | 시도 횟수 (n=8) | 시간 (참고) |
|---|---|---|
| 단순 완전 탐색 (8^8) | 약 1670만 | 수 초 |
| 행마다 한 칸 (8!) | 약 4만 | 0.01초 |
| 백트래킹 + 가지치기 | 약 2천 | 1ms 미만 |
같은 알고리즘 패러다임이라도 가지치기 한 줄의 차이가 시간을 1000배 이상 줄인다. 솔직히 이건 예상 밖이었는데, 학교에서 처음 가지치기 없는 코드와 있는 코드를 같은 N=12에 돌려 보고 한쪽은 끝나지 않고 다른 쪽은 즉시 결과가 떨어지는 모습을 본 후로는 백트래킹의 가치를 "가지치기로 압축하는 완전 탐색"이라는 한 줄로 받아들였다.
백트래킹의 대표 응용과 가지치기 전략
백트래킹이 빛을 발하는 영역을 여섯 가지로 정리하면 다음과 같다(출처: 위키백과 — Backtracking).
| 문제 | 가지치기 핵심 |
|---|---|
| N-Queens | 같은 열·두 대각선 충돌 검사 |
| 스도쿠 (Sudoku) | 가장 후보가 적은 칸 우선·행/열/3×3 박스 충돌 |
| 순열·조합 생성 | 사전식 순서로 진행하면서 중복 차단 |
| 부분집합 합 | 현재 합이 목표를 초과하면 즉시 중단 |
| 미로 찾기 | 방문 표시·벽 검사 |
| 그래프 색칠 | 인접 노드의 색과 다른 색만 시도 |
특히 스도쿠는 백트래킹의 위력을 가장 잘 보여 주는 응용이다. 가장 후보가 적은 빈 칸부터 채워 가는 MRV(Minimum Remaining Values) 휴리스틱과 한 칸을 채우면 다른 칸의 후보를 즉시 줄이는 제약 전파(Constraint Propagation)가 결합되면, 사람이 풀기 어려운 스도쿠도 밀리초 단위로 풀린다. 같은 원리가 SAT 솔버·제약 만족 문제(CSP) 풀이의 토대이다.
좋은 백트래킹 알고리즘을 짜기 위한 세 가지 표준 원칙은 다음과 같다. 첫째, 상태 표현을 가볍게 유지한다. N-Queens의 set 세 개처럼 충돌 검사가 O(1)이 되도록 자료구조를 설계한다. 둘째, 가지치기를 가능한 한 일찍 한다. 트리 깊이 1에서 자를 수 있으면 깊이 5에서 자르지 말 것. 셋째, MRV 같은 휴리스틱으로 분기 순서를 조정한다. 같은 가지치기라도 어느 분기를 먼저 시도하느냐가 시간을 결정한다. 마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "백트래킹은 부분해를 트리로 표현하고 DFS로 탐색하면서 유효하지 않은 경로를 가지치기로 잘라 내는 알고리즘 패러다임이다. N-Queens·스도쿠·순열 생성·부분집합 합·미로 찾기·그래프 색칠이 대표 응용이며, 가지치기의 강도가 알고리즘의 실용성을 결정한다"는 두 문장이 표준 답안 표현으로 통한다.
메타 디스크립션: 백트래킹 알고리즘의 정의와 DFS·완전 탐색과의 차이, N-Queens 고전 풀이로 본 가지치기의 위력, 그리고 스도쿠·순열·미로 찾기 같은 대표 응용과 가지치기 전략을 알고리즘 입문자 관점에서 세심하게 정리합니다.