백트래킹
해를 찾는 과정에서 가능성이 없는 경우를 조기에 배제(pruning) 하여 탐색 공간을 줄이는 알고리즘이다. 완전탐색(Brute-force)과 유사하지만, 단순히 모든 경우를 탐색하지 않고 유망하지 않은 경로를 미리 차단한다는 점에서 효율적이다.
즉, ‘현재 선택이 전체 해답으로 이어질 가능성이 있는가’를 판단하면서 탐색을 진행한다.
대표적으로 순열, 조합, 부분집합, N-Queen, 스도쿠 같은 문제에서 자주 사용된다.
동작원리
백트래킹은 재귀(Recursion) 구조를 기반으로 한다. 기본적인 동작 절차는 다음과 같다.
- 가능한 모든 선택지 중 하나를 선택한다.
- 선택이 유효한지 검사한다.
- 유효하다면 그 다음 단계로 재귀 호출을 수행한다.
- 유효하지 않다면 현재 선택을 취소하고(백트래킹) 다른 선택지를 시도한다.
- 모든 선택지를 탐색할 때까지 위 과정을 반복한다.
이때 가지치기(pruning) 를 얼마나 잘 하느냐에 따라 성능이 크게 달라진다.
불필요한 경로를 빠르게 차단할수록 탐색 횟수를 줄일 수 있다.
백트래킹의 구조적 형태
void backtrack(상태 current) {
if (해를 찾은 경우) {
결과 처리;
return;
}
for (가능한 모든 선택 : candidates) {
if (유망하지 않다면 continue; // 가지치기
선택 수행;
backtrack(다음 상태);
선택 취소; // 원상복구
}
}이 구조에서 핵심은
- 유망성 판단 조건 (promising)
- 상태 복원 (undo / backtrack) 두 가지다. 특히, 백트래킹은 재귀 호출 이후 반드시 이전 상태로 되돌려야 하므로, 상태 복원 과정이 명확해야 한다.
예시 : N-Queen 문제
가장 대표적인 예시로 N-Queen 문제를 들 수 있다.
N×N 체스판 위에 N개의 퀸을 서로 공격하지 않게 배치해야 하는 문제다.
각 행에 퀸을 하나씩 두되, 열과 대각선이 겹치지 않도록 조건을 검사하며 진행한다.
public class NQueen {
static int N;
static int count = 0;
static int[] col; // col[i] = i번째 행에 놓인 퀸의 열 위치
public static void main(String[] args) {
N = 8;
col = new int[N];
solve(0);
System.out.println(count);
}
static void solve(int row) {
if (row == N) {
count++;
return;
}
for (int i = 0; i < N; i++) {
col[row] = i;
if (isPromising(row)) {
solve(row + 1);
}
}
}
static boolean isPromising(int row) {
for (int i = 0; i < row; i++) {
if (col[i] == col[row]) return false; // 같은 열
if (Math.abs(col[row] - col[i]) == row - i) return false; // 대각선
}
return true;
}
}이 코드에서 isPromising() 메서드는 유망성 판단을 수행하는 부분이다.
해당 행까지 배치된 퀸들이 서로 공격하지 않으면 다음 행으로 진행하고, 그렇지 않으면 가지를 잘라낸다.
완전탐색과의 차이
| 구분 | 완전탐색 (Brute Force) | 백트래킹 (Backtracking) |
|---|---|---|
| 탐색 방식 | 가능한 모든 경우 탐색 | 유망하지 않은 경로는 조기 배제 |
| 시간 복잡도 | 지수적 (exponential) | 일반적으로 완전탐색보다 빠름 |
| 구현 난이도 | 비교적 단순 | 유망성 판단과 상태 복원이 필요 |
| 예시 | 순열, 조합 등 단순 탐색 | N-Queen, Sudoku, Graph Coloring 등 |
결국 백트래킹은 완전탐색의 개선된 형태로 볼 수 있다.
가능한 모든 해를 탐색하지만, 불필요한 탐색을 최소화한다는 점이 핵심이다.
가지치기 전략
백트래킹의 효율은 가지치기(pruning)에 달려 있다.
효과적인 가지치기를 위해서는 문제의 특성을 분석해야 한다.
예를 들어,
- N-Queen에서는 대각선 조건을 미리 검사한다.
- 부분집합 문제에서는 현재 합이 목표보다 큰 경우 더 이상 진행하지 않는다.
- 순열 문제에서는 이미 사용한 원소를 다시 선택하지 않는다.
이처럼 제약 조건을 조기에 검증하는 것이 가장 기본적인 가지치기 방법이다.
시간 복잡도
백트래킹의 시간 복잡도는 일반적으로 지수적(Exponential) 복잡도를 가지며, 특정 문제에 따라 달라진다.
최악의 경우 모든 경우의 수를 탐색해야 하므로 복잡도가 매우 높아질 수 있으며, 이는 문제의 조건과 '가지치기(pruning)'에 따라 크게 달라진다.
마무리
백트래킹은 단순한 완전탐색보다 훨씬 효율적인 탐색 방법이다.
재귀 호출 구조와 유망성 판단을 적절히 활용하면 복잡한 탐색 문제를 효과적으로 해결할 수 있다.
문제를 풀 때는 탐색 대상, 제약 조건, 종료 조건, 상태 복원을 명확히 정의하는 것이 중요하다.
이를 습관화하면 백트래킹 문제를 구조적으로 접근할 수 있다.
