백트래킹 — 모든 경우를 탐색하되 빠르게 가지치기하는 법
모든 가능한 경우를 다 해봐야 하는데, 시간이 부족합니다. 어떤 경우는 더 들여다볼 필요 없다는 걸 미리 알 수 있다면 어떨까요?
개념 정의
백트래킹(Backtracking) 은 해를 찾기 위해 모든 가능한 경우를 탐색하되, 조건에 맞지 않으면 즉시 되돌아가는 기법입니다. DFS로 상태 공간 트리를 탐색하면서, 유망하지 않은 노드를 건너뛰어(가지치기) 탐색 효율을 높입니다.
핵심 흐름:
- 선택한다 (Choose)
- 유망한지 검사한다 (Check)
- 유망하지 않으면 되돌아간다 (Backtrack)
- 유망하면 다음 단계로 진행한다
왜 백트래킹이 필요한가
완전 탐색(Brute Force)은 모든 경우를 빠짐없이 살펴봅니다. 하지만 경우의 수가 n!이나 2^n으로 폭발적으로 증가하는 문제에서는 시간 내에 해결할 수 없습니다.
백트래킹은 ** 탐색 도중에 해가 될 수 없는 경로를 빠르게 차단 **합니다. 최악의 경우 완전 탐색과 같지만, 가지치기가 잘 되면 실제 탐색량이 크게 줄어듭니다.
상태 공간 트리
백트래킹은 문제의 해를 트리로 표현합니다. 루트에서 리프까지의 경로가 하나의 후보 해가 됩니다.
순열 {1, 2, 3}의 상태 공간 트리:
[]
/ | \
1 2 3
/ \ / \ / \
2 3 1 3 1 2
| | | | | |
3 2 3 1 2 1
기본 구조: 순열 생성
static int[] arr;
static boolean[] used;
public static void permute(int n, int depth) {
if (depth == n) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = 1; i <= n; i++) {
if (used[i]) continue; // 이미 사용한 숫자는 건너뜀
arr[depth] = i;
used[i] = true;
permute(n, depth + 1); // 다음 위치 결정
used[i] = false; // 되돌리기 (Backtrack)
}
}
used[i] = false가 백트래킹의 핵심입니다. 선택을 취소하고 다른 경로를 탐색합니다.
조합 생성
public static void combine(int n, int r, int start, int depth, int[] selected) {
if (depth == r) {
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i <= n; i++) {
selected[depth] = i;
combine(n, r, i + 1, depth + 1, selected);
// 되돌리기는 다음 반복에서 덮어쓰므로 명시적으로 필요 없음
}
}
start 매개변수가 핵심입니다. 이전에 선택한 숫자 다음부터 탐색하여 중복을 방지합니다.
N-Queen 문제
N×N 체스판에 N개의 퀸을 서로 공격하지 못하도록 배치하는 문제입니다. 백트래킹의 대표적인 예제입니다.
가지치기 조건
퀸은 같은 행, 같은 열, 같은 대각선에 있으면 서로 공격합니다. 행마다 퀸을 하나씩 배치하면 행 충돌은 자동으로 해결됩니다.
행마다 퀸을 하나씩 배치하며, 유효하지 않으면 즉시 되돌아갑니다.
static int n, count = 0;
static int[] queens; // queens[row] = col
public static void solve(int row) {
if (row == n) { count++; return; }
for (int col = 0; col < n; col++) {
if (isValid(row, col)) {
queens[row] = col;
solve(row + 1);
}
}
}
유효성 검사에서는 같은 열과 대각선 충돌을 확인합니다. 행 충돌은 행마다 하나씩 배치하므로 자동으로 해결됩니다.
private static boolean isValid(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col) return false; // 같은 열
if (Math.abs(queens[i] - col) == Math.abs(i - row)) return false; // 대각선
}
return true;
}
최적화: 비트마스크 활용
열, 좌대각선, 우대각선을 비트마스크로 관리하면 O(1)에 유효성을 검사할 수 있습니다.
static int count = 0;
public static void solveWithBitmask(int row, int cols, int diag1, int diag2) {
if (row == n) {
count++;
return;
}
// 사용 가능한 열: 전체에서 사용 중인 열/대각선을 빼기
int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
while (available != 0) {
int pos = available & (-available); // 최하위 비트
available -= pos;
solveWithBitmask(row + 1,
cols | pos,
(diag1 | pos) << 1,
(diag2 | pos) >> 1);
}
}
부분 집합 생성
원소를 포함하거나 포함하지 않는 두 가지 선택으로 모든 부분 집합을 생성합니다.
public static void subsets(int[] nums, int index, List<Integer> current) {
if (index == nums.length) {
System.out.println(current);
return;
}
// 현재 원소를 포함하지 않는 경우
subsets(nums, index + 1, current);
// 현재 원소를 포함하는 경우
current.add(nums[index]);
subsets(nums, index + 1, current);
current.remove(current.size() - 1); // 되돌리기
}
가지치기 전략
가지치기의 효과는 ** 얼마나 빨리 유망하지 않은 경로를 차단하느냐 **에 달려 있습니다.
유효성 검사 (Feasibility Check)
현재 상태에서 조건을 만족하는지 확인합니다. N-Queen의 열/대각선 충돌 검사가 대표적입니다.
경계값 검사 (Bounding)
현재까지의 값이 최적값을 넘지 못하는 게 확실하면 탐색을 중단합니다.
// 배낭 문제에서의 가지치기
public static void knapsack(int index, int weight, int value) {
// 가지치기: 남은 물건을 모두 넣어도 현재 최적값을 못 넘으면 중단
if (value + upperBound(index) <= bestValue) return;
if (weight > capacity) return;
if (index == n) {
bestValue = Math.max(bestValue, value);
return;
}
// 현재 물건을 넣는 경우
knapsack(index + 1, weight + w[index], value + v[index]);
// 현재 물건을 넣지 않는 경우
knapsack(index + 1, weight, value);
}
대칭성 제거
N-Queen에서 대칭/회전 해를 제거하면 탐색량이 줄어듭니다. 첫 행의 퀸을 절반 열까지만 탐색하고 결과를 2배 하는 방식이 있습니다.
DFS와 백트래킹의 관계
백트래킹은 DFS를 기반으로 합니다. 차이점은 ** 가지치기의 유무 **입니다.
| 구분 | DFS | 백트래킹 |
|---|---|---|
| 탐색 방식 | 깊이 우선 | 깊이 우선 |
| 가지치기 | 없음 (모든 노드 방문) | 유망하지 않으면 건너뜀 |
| 용도 | 그래프 탐색 전반 | 제약 조건이 있는 최적화/열거 |
백엔드/실무에서의 연결
SQL 쿼리 최적화
데이터베이스의 쿼리 옵티마이저는 여러 실행 계획을 탐색하며, 비용이 높은 계획을 가지치기합니다. 이것이 백트래킹의 변형입니다.
정규 표현식 엔진
NFA 기반 정규 표현식 엔진은 백트래킹으로 패턴을 매칭합니다. 잘못 작성된 정규 표현식이 느린 이유 중 하나가 과도한 백트래킹(ReDoS 공격)입니다.
Spring의 경로 매칭
URL 패턴에 와일드카드가 있을 때, 여러 패턴 후보를 탐색하며 가장 구체적인 패턴을 찾는 과정에도 백트래킹 개념이 사용됩니다.
스도쿠 풀기
스도쿠는 전형적인 백트래킹 문제입니다. 빈 칸에 1~9를 넣어보고, 규칙에 어긋나면 되돌립니다.
public static boolean solveSudoku(int[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] != 0) continue;
for (int num = 1; num <= 9; num++) {
if (isValidPlacement(board, row, col, num)) {
board[row][col] = num;
if (solveSudoku(board)) return true;
board[row][col] = 0; // 되돌리기
}
}
return false; // 1~9 모두 안 되면 이전으로 되돌아감
}
}
return true; // 모든 칸이 채워짐
}
주의할 점
되돌리기(복원)를 빠뜨리는 실수
백트래킹에서 가장 흔한 버그는 ** 상태 복원을 빠뜨리는 것 **입니다. used[i] = true로 설정한 뒤 재귀가 끝나면 반드시 used[i] = false로 되돌려야 합니다. 이 한 줄을 빠뜨리면 이후 탐색에서 해당 선택지가 영영 차단됩니다.
가지치기 없이 완전 탐색으로 제출하는 실수
가지치기를 하지 않으면 백트래킹이 아니라 단순 브루트포스입니다. N-Queen에서 가지치기 없이 모든 배치를 시도하면 N^N가지를 탐색하지만, 열/대각선 검사만 추가해도 탐색량이 수십 배 이상 줄어듭니다.
정규 표현식의 과도한 백트래킹 (ReDoS)
NFA 기반 정규 표현식 엔진은 내부적으로 백트래킹을 사용합니다. (a+)+$ 같은 패턴에 "aaaaaaaaab"를 매칭하면 지수적 백트래킹이 발생하여 서버가 멈출 수 있습니다. 이를 ReDoS(Regular expression Denial of Service)라고 합니다.
정리
| 기법 | 시간 복잡도 | 가지치기 효과 |
|---|---|---|
| 순열 | O(n!) | 중복 제거로 개선 가능 |
| 조합 | O(2^n) | 시작 인덱스로 중복 방지 |
| N-Queen | O(n!) → 가지치기로 대폭 감소 | 열/대각선 검사로 조기 차단 |
| 부분 집합 | O(2^n) | 합계 초과 시 중단 가능 |
기억할 포인트:
- 백트래킹 = DFS + 가지치기입니다.
- ** 선택 → 검사 → 되돌리기** 패턴을 익히면 대부분의 백트래킹 문제에 적용할 수 있습니다.
- 가지치기를 얼마나 효과적으로 하느냐가 성능을 결정합니다.
- 실무에서도 쿼리 옵티마이저, 정규 표현식 엔진 등에서 백트래킹 개념이 사용됩니다.