백트래킹의 정의
백트래킹이란 모든 경우의 수를 재귀적으로 탐색하면서, 조건에 맞지 않는 경로는 되돌아가서 가지치기(pruning)하는 알고리즘 기법이다.
쉽게 말하면 "일단 가보고, 안 되면 돌아온다"는 전략이다. 모든 선택지를 하나씩 시도해보되, 현재 경로가 유망하지 않다고 판단되면 더 깊이 들어가지 않고 이전 단계로 되돌아가서 다른 선택지를 시도한다.
백 트래킹의 대표적인 예시중 하나인 BFS와 DFS 탐색법이다.
DFS와 백트래킹의 관계
백트래킹을 처음 접하면 DFS(깊이우선탐색)와 헷갈리기 쉽다.
DFS는 트리나 그래프를 깊이 우선으로 순회하는 탐색 알고리즘이다. 한 방향으로 끝까지 내려간 뒤 돌아와서 다음 방향을 탐색한다.
백트래킹은 DFS에 가지치기(pruning) 개념이 추가된 것이다. 즉, 백트래킹 = DFS가 아니라 백트래킹의 구현 방법 중 하나가 DFS인 것이다. BFS로도 백트래킹을 구현할 수 있지만, 대부분의 경우 DFS를 사용하여 구현한다.
핵심 차이를 정리하면 다음과 같다.
| 구분 | DFS | 백트래킹 |
|---|---|---|
| 목적 | 그래프/트리 순회 | 조건을 만족하는 해 탐색 |
| 가지치기 | 없음 (끝까지 탐색) | 있음 (유망하지 않으면 중단) |
| 관계 | 탐색 알고리즘 | DFS를 활용한 문제 해결 기법 |
백트래킹의 일반적인 구현 패턴
백트래킹은 세 단계로 구성된다: 선택 → 탐색 → 선택 취소
void backtrack(현재 상태, 선택지들, 방문 기록) {
// 종료 조건 (base case)
if (종료 조건을 만족하면) {
결과 저장;
return;
}
for (각 선택지를 순회) {
if (이미 방문했거나 유효하지 않으면) continue; // 가지치기
선택 (방문 표시) // 1. 선택
backtrack(다음 상태, 선택지들, 방문 기록) // 2. 재귀 탐색
선택 취소 (방문 해제) // 3. 원상복구
}
}여기서 중요한 점은 각 재귀 호출마다 정확히 하나의 결정(decision)을 내린다는 것이다. 그리고 그 선택은 이전까지의 모든 결정과 일관성이 있어야 한다.
또한 각 재귀 호출에는 두 가지 정보가 필요하다:
- 아직 처리하지 않은 남은 입력 데이터
- 지금까지 내린 결정들의 요약 정보 (이 요약은 효율을 위해 최대한 작게 유지해야 한다)
대표 예제 1: N-Queens Problem
문제 설명
n×n 체스보드 위에 서로 공격받지 않도록 n개의 Queen을 배치할 수 있는가? 가능하다면 그런 배치는 총 몇 가지인가?
Queen은 같은 행, 같은 열, 같은 대각선에 있는 말을 공격할 수 있으므로, 어떤 두 Queen도 같은 행·열·대각선에 있으면 안 된다.
접근 방식
행 단위로 Queen을 한 개씩 배치한다. r번째 행에 Queen을 놓을 때, 1~n열 중 이전에 놓은 Queen들과 충돌하지 않는 열을 찾아서 배치한다.
recursive call 시 넘겨주는 정보:
- 비어있는 row들의 정보 (아직 Queen을 놓지 않은 행)
- 이전에 배치한 Queen들의 정보 (충돌 검사를 위해)
충돌 검사
Q[i]를 i번째 행에 놓인 Queen의 열 번호라 할 때, r번째 행의 j열에 Queen을 놓으려면 이전 모든 행 i(1 ≤ i ≤ r-1)에 대해 다음을 확인한다:
Q[i] == j→ 같은 열 (충돌)Q[i] == j + r - i→ 같은 대각선 (충돌)Q[i] == j - r + i→ 같은 대각선 (충돌)
세 조건 모두 해당하지 않으면 배치가 가능하다.
의사 코드
PlaceQueens(Q[1..n], r):
if r = n + 1
print Q[1..n] // 모든 행에 Queen을 다 배치한 경우 → 해 출력
else
for j ← 1 to n
legal ← TRUE
for i ← 1 to r - 1
if (Q[i] = j) or (Q[i] = j+r-i) or (Q[i] = j-r+i)
legal ← FALSE
if legal
Q[r] ← j
PlaceQueens(Q[1..n], r + 1) // 재귀!4-Queens의 경우, 재귀 트리를 그려보면 대부분의 가지가 중간에 잘리고 유효한 배치만 리프 노드에 도달하는 것을 확인할 수 있다.
대표 예제 2: Subset Sum
문제 설명
양의 정수 집합 X와 목표값 T가 주어졌을 때, X의 부분집합 중 합이 T가 되는 것이 존재하는가?
X = {8, 6, 7, 5, 3, 10, 9},T = 15→ TRUE ({8,7}, {5,10}, {6,9}, {7,5,3} 등)X = {11, 6, 5, 1, 7, 13, 12},T = 15→ FALSE (합이 15가 되는 부분집합 없음)
Base Cases
T = 0→ 항상 TRUE (공집합의 합은 0)T < 0또는X가 공집합 → 항상 FALSE
General Case
X의 임의의 원소 x에 대해, 합이 T인 부분집합이 존재한다면 그것은:
- x를 포함하거나 →
SubsetSum(X \ {x}, T - x) - x를 포함하지 않거나 →
SubsetSum(X \ {x}, T)
둘 중 하나라도 TRUE이면 결과는 TRUE이다.
의사 코드
SubsetSum(X, T):
if T = 0
return TRUE
else if T < 0 or X = ∅
return FALSE
else
x ← any element of X
with ← SubsetSum(X \ {x}, T - x) // x를 포함하는 경우
wout ← SubsetSum(X \ {x}, T) // x를 포함하지 않는 경우
return (with ∨ wout)recursive call 시 넘겨주는 정보:
- 포함 여부를 아직 결정하지 않은 나머지 원소들
- 남은 target 값 (기존 T에서 선택한 원소의 값을 뺀 나머지)
이처럼 각 원소에 대해 "포함한다 / 포함하지 않는다" 두 갈래로 재귀를 돌리는 것이 핵심이다.
유망성 판단 (Pruning)
백트래킹의 핵심은 유망성(promising) 판단이다. 해당 노드의 범위 내에서 조건을 추가하여 값의 유망성을 판단한다는 의미이다.
예를 들어 a + b + c + d = 21이고, 각 변수의 범위가 1~100이라 하자. 만약 a = 21이 되면 나머지 b, c, d가 아무리 작아도 최소 1+1+1 = 3이므로 합이 24 이상이 되어 21을 절대 만들 수 없다. 따라서 a > 20인 경우는 탐색하지 않는다. 마찬가지로 a가 정해진 후 b > 20이면 탐색하지 않는 식으로 가지치기를 할 수 있다.
이렇게 하면 모든 경우를 완전탐색하는 것보다 탐색해야 할 자원을 크게 줄일 수 있다.
정리
| 항목 | 내용 |
|---|---|
| 핵심 아이디어 | 모든 경우를 탐색하되, 유망하지 않으면 되돌아간다 |
| 구현 패턴 | 선택 → 재귀 탐색 → 선택 취소 |
| 주 구현 방식 | DFS (깊이우선탐색) |
| 가지치기 | 유망하지 않은 경로를 조기에 차단하여 효율 향상 |
| 대표 문제 | N-Queens, Subset Sum, 순열/조합, 스도쿠 등 |
