백트래킹 (Backtracking)

정의

백트래킹 (Backtracking) 은 DFS + 가지치기 (pruning) 로 모든 경우를 탐색하되, 불가능한 후보를 조기 제거하여 탐색 공간을 극적으로 줄이는 알고리즘. 순열, 조합, N-Queens, Sudoku 등 제약 충족 문제 (CSP) 에서 핵심 기법.

문제 상황과 동기

모든 가능한 해 조합을 생성·검증해야 하는 문제.

• naive: N! 또는 2^N 의 모든 케이스를 생성 후 각각 검증. 지수 시간.
• 백트래킹: 탐색 중 불가능함이 확정되면 즉시 돌아가 (backtrack) 그 서브트리 전부를 건너뛴다.

N = 8 인 N-Queens 에서 naive 는 8!×8 = 322,560 개 위치 점검. 백트래킹은 평균 ~1,000 회 이하로 줄어든다. 핵심 통찰: “지금까지 선택한 부분 해가 제약 위반이면 더 이상 진행 무의미”.

실무에서는 조합 최적화 (스케줄링, SAT 솔버, 게임 AI) 의 base 알고리즘.

시각화

핵심 아이디어

invariant: 현재 경로는 항상 제약을 만족. 다음 선택지를 추가할 때 제약을 깨면 즉시 되돌아간다.

초기: 공집합 또는 초기 상태
재귀(현재 경로):
    if 목표 상태: 해 기록 / 종료
    for 선택지 c in 후보들:
        if c 가 현재 경로와 충돌: continue  // 가지치기
        경로.push(c)
        재귀(경로)
        경로.pop()                          // 백트랙

각 재귀 단계마다 이 분기는 불가면 전체 서브트리 탐색 생략.

알고리즘

N-Queens 예제

solve_nqueens(n, row, cols, diag1, diag2):
    # cols[c] = true  이면 c 열 사용 중
    # diag1[r+c] = true 이면 / 대각선 사용 중
    # diag2[r-c+n-1] = true 이면 \ 대각선 사용 중
    if row == n:
        해 하나 출력
        return
    for c in 0..n-1:
        if cols[c] or diag1[row+c] or diag2[row-c+n-1]:
            continue  # 가지치기
        cols[c] = diag1[row+c] = diag2[row-c+n-1] = true
        solve_nqueens(n, row+1, cols, diag1, diag2)
        cols[c] = diag1[row+c] = diag2[row-c+n-1] = false

순열 생성

permutation(arr, used, path):
    if path.size == arr.size:
        출력 path
        return
    for i in 0..arr.size-1:
        if used[i]: continue
        used[i] = true
        path.push(arr[i])
        permutation(arr, used, path)
        path.pop()
        used[i] = false

구현

// 4-Queens 모든 해 출력
#include <bits/stdc++.h>
using namespace std;
int n, cnt;
bool col[20], d1[40], d2[40];  // diag1[r+c], diag2[r-c+n-1]
void solve(int r) {
  if (r == n) {
      cnt++;
      return;
  }
  for (int c = 0; c < n; c++) {
      if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
      col[c] = d1[r + c] = d2[r - c + n - 1] = true;
      solve(r + 1);
      col[c] = d1[r + c] = d2[r - c + n - 1] = false;
  }
}
int main() {
  cin >> n;
  solve(0);
  cout << cnt << "\n";
}

# 4-Queens 모든 해 개수
def solve(r, n, col, d1, d2):
  if r == n:
      return 1
  cnt = 0
  for c in range(n):
      if col[c] or d1[r + c] or d2[r - c + n - 1]:
          continue
      col[c] = d1[r + c] = d2[r - c + n - 1] = True
      cnt += solve(r + 1, n, col, d1, d2)
      col[c] = d1[r + c] = d2[r - c + n - 1] = False
  return cnt
​
n = int(input())
col = [False] * 20
d1 = [False] * 40
d2 = [False] * 40
print(solve(0, n, col, d1, d2))

// 4-Queens 모든 해 개수
import java.util.*;
public class Main {
  static int n, cnt;
  static boolean[] col = new boolean[20], d1 = new boolean[40], d2 = new boolean[40];
  static void solve(int r) {
      if (r == n) { cnt++; return; }
      for (int c = 0; c < n; c++) {
          if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
          col[c] = d1[r + c] = d2[r - c + n - 1] = true;
          solve(r + 1);
          col[c] = d1[r + c] = d2[r - c + n - 1] = false;
      }
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      solve(0);
      System.out.println(cnt);
  }
}

4

2

8

92

복잡도

최악 케이스에는 naive 와 차이 없지만, 잘 설계된 제약이 있으면 실용 시간으로 내려온다.

변형 / 활용

함정

1. 가지치기 조건 빠뜨림

가지치기를 안 하면 시간초과. 예: N-Queens 에서 대각선 검사를 생략하면 O(N^N).

2. 백트랙 복원 누락

// 잘못: path.push(x) 후 재귀, pop() 없음
// 올바름:
path.push(x);
solve(path);
path.pop();  // 반드시 복원

3. 상태 공유 vs 복사

전역 상태를 쓰면 백트랙 시 복원 필수. 지역 복사는 안전하지만 메모리 증가.

// 전역 상태 (빠름, 복원 필수)
bool used[N];
void solve() {
    used[i] = true;
    solve();
    used[i] = false;  // 복원
}

// 지역 복사 (안전, 느림)
void solve(vector<bool> used) {
    used[i] = true;
    solve(used);  // 복사본 전달, 자동 복원
}

4. 중복 해 제거

순열에서 같은 값이 여러 개면 중복 해 발생. 정렬 후 arr[i] == arr[i-1] && !used[i-1] 면 skip 으로 방지.

최적화

BOJ 연습 문제

참고

• 깊이 우선 탐색
• Bitmask
• 순열과 조합