[백트래킹] 2. 가지치기와 최적화

가지치기가 왜 중요한가

백트래킹의 성능은 가지치기를 얼마나 잘 하느냐에 달려 있다. 가지치기 없는 백트래킹은 그냥 완전탐색이고, 가지치기를 잘 설계하면 탐색 공간을 수십, 수백 배 줄일 수 있다.

N-Queens 문제에서 8×8 체스판의 전체 경우의 수는 8^8 = 16,777,216개다. 하지만 같은 열 검사만 추가해도 8! = 40,320개로 줄고, 대각선 검사까지 하면 실제로 방문하는 노드는 수천 개 수준이 된다.

가지치기 전략

제약 조건 기반 가지치기

문제에서 주어진 제약 조건을 그대로 유망성 검사에 활용하는 방식이다. 가장 기본적이면서 가장 중요하다.

N-Queens에서 "같은 열, 같은 대각선 금지"가 바로 이것이다. 조건을 위반하는 선택을 아예 시도하지 않는다.

if (!isPromising(row, col)) continue;

문제를 읽었을 때 "~하면 안 된다", "~을 만족해야 한다"라는 조건이 보이면, 그걸 곧바로 가지치기 조건으로 쓸 수 있는지 따져봐야 한다.

한계값 가지치기 (Bound Pruning)

"최솟값을 구하라"는 최적화 문제에서 쓰는 전략이다. 현재까지의 비용이 이미 알려진 최솟값 이상이면, 더 탐색해봐야 더 나은 답이 나올 수 없으므로 즉시 되돌아간다.

static int minResult = Integer.MAX_VALUE;

void backtrack(int depth, int currentCost) {
    if (currentCost >= minResult) return;

    if (depth == 목표) {
        minResult = Math.min(minResult, currentCost);
        return;
    }
    // ...
}

• minResult는 지금까지 찾은 최선의 답이다.
• 탐색 중간에 currentCost가 minResult에 도달하면 그 이후는 볼 필요가 없다.

이 전략이 효과를 발휘하려면 좋은 답을 빨리 찾는 것이 중요하다. 초기에 minResult가 클수록 가지치기가 덜 일어나기 때문이다.

대칭성 제거

동일한 답이 순서만 바뀌어 여러 번 나오는 경우, 대칭을 제거하면 탐색 공간을 절반 이상 줄일 수 있다.

예를 들어 부분집합 문제에서 {1, 2}와 {2, 1}은 같은 집합이다. 이걸 방지하려면 이전에 선택한 원소보다 큰 것만 고르도록 제한한다.

void subsets(int start, List<Integer> current) {
    결과 처리(current);

    for (int i = start; i < n; i++) {
        current.add(arr[i]);
        subsets(i + 1, current);
        current.remove(current.size() - 1);
    }
}

• start 파라미터가 핵심이다. 이전에 선택한 인덱스 이후부터만 탐색한다.
• 순열이면 start 없이 전체를 순회하고, 조합이면 start로 제한한다.

탐색 순서 최적화

가지치기와 함께, 어떤 순서로 선택지를 시도하느냐도 성능에 큰 영향을 미친다.

가장 제약이 강한 것부터 (MRV)

선택지가 가장 적은 변수를 먼저 처리하면, 초반에 가지가 많이 잘려서 전체 탐색 공간이 줄어든다. 이걸 MRV(Minimum Remaining Values) 전략이라고 한다.

스도쿠를 예로 들면, 빈 칸 중에서 넣을 수 있는 숫자가 가장 적은 칸부터 채우는 것이다. 선택지가 1개뿐인 칸을 먼저 처리하면 연쇄적으로 다른 칸의 선택지도 줄어든다.

최적해에 가까운 것부터

"최솟값을 구하라"는 문제에서 큰 것부터 시도하면, 초반에 좋은 답을 빨리 찾아서 한계값 가지치기가 더 강하게 작동한다.

예를 들어 BOJ17136 색종이 붙이기에서 색종이를 5×5부터 시도하면, 큰 색종이로 많이 덮어서 최솟값이 빨리 줄어들고, 이후 가지치기가 더 효과적이다.

for (int size = 5; size >= 1; size--) {
    // 큰 색종이부터 시도
}

시간복잡도 분석

백트래킹의 시간복잡도는 정확히 계산하기 어렵다. 가지치기 효과는 입력에 따라 달라지기 때문이다. 그래서 보통 최악의 경우를 기준으로 판단한다.

대표적인 시간복잡도

유형	최악 시간복잡도	설명
순열	O(N!)	N개 원소의 모든 순열
조합	O(2^N)	N개 원소의 모든 부분집합
N-Queens	O(N!)	실제로는 가지치기로 훨씬 적음
스도쿠	O(9^81) 이론상	실제로는 제약 전파로 매우 빠름

이론적 최악과 실제 실행 시간의 괴리가 크다는 걸 인지해야 한다. 면접에서 "백트래킹의 시간복잡도는?"이라고 물으면, 최악을 말하되 "가지치기로 실제로는 훨씬 빠르다"고 덧붙이는 게 좋다.

시간 내에 들어올지 판단하는 법

코딩테스트에서는 이론적 복잡도보다 실전적 감각이 더 중요하다.

1. N이 20 이하면 → O(2^N) 이하의 백트래킹이 보통 통과
2. N이 10 이하면 → O(N!) 도 가능
3. N이 30 이상이면 → 순수 백트래킹으로는 어렵고, DP나 다른 기법이 필요할 가능성이 높다

가지치기 설계 체크리스트

새로운 백트래킹 문제를 만났을 때, 아래 순서로 가지치기를 설계하면 된다.

1. 제약 조건 나열 — 문제에서 "~하면 안 된다"는 조건을 전부 뽑는다
2. 유망 함수 작성 — 각 조건을 선택 전에 검사하는 함수로 만든다
3. 한계값 설정 — 최적화 문제면 현재 비용과 최솟값을 비교한다
4. 탐색 순서 결정 — 제약이 강한 것부터, 또는 최적해에 가까운 것부터
5. 대칭 제거 — 같은 답이 여러 번 나오는지 확인하고, 순서를 강제한다

자주 하는 실수

가지치기 조건이 너무 느슨한 경우

가지치기를 넣었는데도 시간 초과가 나면, 조건을 더 강화할 수 있는지 따져봐야 한다. 예를 들어 "남은 색종이로 남은 1을 다 덮을 수 있는가?"처럼 미래의 가능성까지 계산하는 가지치기를 추가할 수 있다.

한계값을 갱신하지 않는 경우

// 잘못된 코드 — minResult가 갱신되지 않음
if (depth == 목표) {
    System.out.println(currentCost);
    return;
}

// 올바른 코드
if (depth == 목표) {
    minResult = Math.min(minResult, currentCost);
    return;
}

답을 찾을 때마다 minResult를 갱신해야 이후 가지치기가 점점 강해진다. 갱신을 안 하면 가지치기가 전혀 작동하지 않는다.

정리

핵심 포인트	설명
제약 조건 → 가지치기	문제의 제약을 그대로 유망성 검사로
한계값 가지치기	현재 비용 ≥ 최솟값이면 즉시 중단
탐색 순서가 성능을 좌우	큰 것부터, 제약 강한 것부터
대칭 제거	start 파라미터로 중복 방지

다음 문서에서는 실전에서 자주 나오는 백트래킹 유형을 패턴별로 정리하고, 면접 대비 Q&A를 다룬다.

---