백트래킹

가능한 모든 후보를 시도하되, 유효하지 않다고 판단되는 순간 즉시 되돌아가는(가지치기) 탐색 알고리즘입니다.

핵심 개념

[ 상태 공간 트리 — N=3 순열 예시 ]

                  start
           /        |        \
          1         2         3
        /   \     /   \     /   \
       2     3   1     3   1     2
       |     |   |     |   |     |
       3     2   3     1   2     1

완전 탐색: 모든 리프 방문 (6개)
백트래킹: 조건 위반 시 해당 가지 전체 건너뜀

기본 구조

void backtrack(상태) {
    if (종료 조건) {
        결과 저장;
        return;
    }

    for (후보 in 후보_목록) {
        if (!유효한(후보)) continue;   // 가지치기

        선택(후보);                    // 상태 변경
        backtrack(다음 상태);          // 재귀 탐색
        취소(후보);                    // 상태 복원 ← 핵심
    }
}

"선택 → 탐색 → 취소" 3단계가 핵심. 취소(복원)가 없으면 백트래킹이 아님.

패턴 1: 순열 (Permutation)

n개 중 r개를 순서 있게 나열 — nPr

static int[] arr = {1, 2, 3};
static boolean[] used = new boolean[3];
static int[] result = new int[3];

void permutation(int depth, int r) {
    if (depth == r) {
        System.out.println(Arrays.toString(result));
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        if (used[i]) continue;         // 이미 선택한 원소 건너뜀

        used[i] = true;                // 선택
        result[depth] = arr[i];
        permutation(depth + 1, r);
        used[i] = false;               // 취소
    }
}
// permutation(0, 3) → {1,2,3}, {1,3,2}, {2,1,3}, ... (6가지)

패턴 2: 조합 (Combination)

n개 중 r개를 순서 없이 선택 — nCr

순열과의 차이: start 인덱스로 이전 원소 재선택을 막음.

static int[] arr = {1, 2, 3, 4};
static int[] result = new int[2];

void combination(int start, int depth, int r) {
    if (depth == r) {
        System.out.println(Arrays.toString(result));
        return;
    }

    for (int i = start; i < arr.length; i++) {
        result[depth] = arr[i];            // 선택
        combination(i + 1, depth + 1, r); // i+1부터 — 순서 중복 방지
        // 취소: 배열 덮어쓰므로 별도 복원 불필요
    }
}
// combination(0, 0, 2) → {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}

패턴 3: 부분집합 (Subset)

n개 원소로 만들 수 있는 모든 부분집합 — 2^n개

각 원소에 대해 "포함 / 미포함" 두 선택지.

static int[] arr = {1, 2, 3};
static boolean[] selected = new boolean[3];

void subset(int idx) {
    if (idx == arr.length) {
        for (int i = 0; i < arr.length; i++) {
            if (selected[i]) System.out.print(arr[i] + " ");
        }
        System.out.println();
        return;
    }

    selected[idx] = true;   // 포함
    subset(idx + 1);
    selected[idx] = false;  // 미포함
    subset(idx + 1);
}
// {} {3} {2} {2,3} {1} {1,3} {1,2} {1,2,3} (8가지)

패턴 4: N-Queens (가지치기가 핵심)

N×N 체스판에 N개의 퀸을 서로 공격 못 하게 배치.

static int N = 4;
static int[] queen = new int[N];   // queen[row] = col

int solve(int row) {
    if (row == N) return 1;        // N개 모두 배치 성공

    int count = 0;
    for (int col = 0; col < N; col++) {
        if (!isValid(row, col)) continue;   // 가지치기

        queen[row] = col;                   // 배치
        count += solve(row + 1);
        // 취소: 다음 반복에서 queen[row] 덮어씀
    }
    return count;
}

boolean isValid(int row, int col) {
    for (int r = 0; r < row; r++) {
        if (queen[r] == col) return false;               // 같은 열
        if (Math.abs(queen[r] - col) == row - r) return false;  // 대각선
    }
    return true;
}

[ N=4 탐색 과정 — 가지치기 효과 ]

배치 시도:  256가지 (4^4, 완전 탐색)
실제 탐색:  ~50가지  (가지치기 후)
유효한 배치: 2가지

순열 vs 조합 vs 부분집합

순열조합부분집합
경우의 수nPr = n!/(n-r)!nCr = n!/r!(n-r)!2^n
순서있음없음없음
중복 방지visited[] 배열start 인덱스—
예시{1,2} ≠ {2,1}{1,2} = {2,1}{1}, {2}, {1,2}

가지치기 전략

가지치기의 질이 성능을 결정. 조건이 구체적일수록 잘라내는 가지가 많아짐.

[ 가지치기 조건 예시 ]

합 제한:   현재까지 합이 목표 초과 → 더 더해도 소용없음 → 중단
N-Queens:  같은 열 / 대각선에 퀸 존재 → 해당 열 건너뜀
방문 제한: 이미 방문한 노드 → 재방문 건너뜀
범위 초과: 인덱스가 배열 범위 벗어남 → 즉시 return

시간복잡도

가지치기 효과가 있어서 최선/평균/최악이 크게 갈림.

상황복잡도
완전 탐색 (가지치기 없음)O(n!) or O(2^n)
가지치기 적용 후문제마다 다름 — 분석 어려움
실용적 판단 기준n ≤ 10 이면 순열(n!), n ≤ 20 이면 부분집합(2^n) 가능

자주 하는 실수

상태 복원 누락

// X visited 복원 안 함 → 뒤 경로에서 원소가 막혀있음
used[i] = true;
backtrack(depth + 1);
// used[i] = false; ← 빠뜨리면 오답

// O
used[i] = true;
backtrack(depth + 1);
used[i] = false;

조합에서 start 누락

// X i=0부터 시작 → 순열처럼 동작 (순서 다른 중복 발생)
for (int i = 0; i < n; i++) { ... }

// O start부터 시작 → 이전 원소 재선택 방지
for (int i = start; i < n; i++) { ... }

가지치기 조건 범위 오류

// X 너무 엄격한 가지치기 → 유효한 답을 잘라낼 수 있음
if (sum >= target) return;   // sum == target인 경우도 잘라냄

// O
if (sum > target) return;    // 초과할 때만 자름

핵심 정리

CSLOG에서 보기