[백트래킹] 1. 기본 개념

왜 백트래킹을 알아야 할까

코딩테스트에서 "모든 경우를 따져야 하는데, 전부 따지면 시간 초과"인 문제를 자주 만난다. 백트래킹은 불필요한 경우를 일찍 걸러내면서 모든 가능성을 탐색하는 기법이다. 완전탐색의 효율화 버전이라고 보면 된다.

완전탐색에서 백트래킹으로

완전탐색이란

완전탐색(Brute Force)은 가능한 모든 경우의 수를 하나하나 시도해보는 방식이다. 정답을 반드시 찾을 수 있지만, 경우의 수가 폭발적으로 늘어나면 시간 안에 끝나지 못한다.

예를 들어 4자리 비밀번호를 맞추려면 0000~9999까지 10,000개를 다 시도하면 된다. 이게 완전탐색이다. 하지만 "첫 번째 자리가 홀수여야 한다"는 조건이 있다면? 첫 자리가 짝수인 5,000개는 시도할 필요가 없다. 이렇게 조건에 맞지 않는 가지를 잘라내는 것이 백트래킹의 핵심이다.

둘의 관계

완전탐색과 백트래킹은 별개의 알고리즘이 아니다. 백트래킹은 완전탐색에 가지치기(pruning)를 더한 것이다.

가지치기가 없으면 완전탐색이고, 있으면 백트래킹이다. 그래서 백트래킹 문제를 풀 때는 항상 "어떤 조건으로 가지를 칠 것인가"를 먼저 생각해야 한다.

상태 공간 트리

백트래킹을 이해하려면 상태 공간 트리(State Space Tree)를 먼저 알아야 한다. 이건 문제의 모든 선택지를 트리 형태로 펼쳐놓은 것이다.

{1, 2, 3}에서 순열을 구하는 문제를 생각해보자. 첫 번째 자리에 1, 2, 3 중 하나를 고르고, 두 번째 자리에 남은 것 중 하나를 고르고... 이 과정을 트리로 그리면 이렇다.

트리의 각 노드는 "현재까지의 선택 상태"이고, 리프 노드(맨 아래)가 하나의 완성된 답이다. 완전탐색은 이 트리의 모든 리프를 방문한다. 백트래킹은 중간 노드에서 "이 방향은 답이 안 된다"고 판단되면 더 내려가지 않고 되돌아간다.

백트래킹의 동작 원리

백트래킹의 핵심 동작은 세 단계로 나눌 수 있다.

1. 선택(Choose) — 현재 단계에서 가능한 선택지 중 하나를 고른다
2. 검증(Validate) — 이 선택이 유망한지(promising) 확인한다
3. 되돌리기(Undo) — 해당 선택지의 탐색이 끝나면 선택을 취소하고 다음 선택지로 넘어간다

여기서 가장 중요한 건 되돌리기다. 재귀 호출이 끝나고 돌아왔을 때, 상태를 반드시 호출 전으로 복구해야 한다. 이걸 빠뜨리면 이전 선택의 흔적이 남아서 이후 탐색이 전부 오염된다.

기본 코드 구조

백트래킹의 뼈대는 거의 모든 문제에서 동일하다.

void backtrack(int depth) {
    if (depth == 목표) {
        결과 처리;
        return;
    }

    for (선택지 : 가능한 선택지들) {
        if (!유망한가(선택지)) continue;

        상태 변경(선택지);
        backtrack(depth + 1);
        상태 복구(선택지);
    }
}

• depth — 현재 몇 번째 선택을 하고 있는지. 재귀의 깊이.
• 목표 — 선택을 모두 마친 조건. 리프 노드에 도달한 것.
• 유망한가 — 이 선택지를 골랐을 때 답이 나올 가능성이 있는지 판단하는 함수.
• 상태 변경 / 상태 복구 — 항상 쌍으로 존재해야 한다. 하나만 있으면 버그.

예시로 이해하기 — N-Queens

N-Queens는 백트래킹의 대표 문제다. N×N 체스판에 N개의 퀸을 서로 공격하지 못하게 배치하는 문제다.

퀸은 같은 행, 같은 열, 같은 대각선에 있는 말을 공격할 수 있다. 그래서 각 행에 퀸을 하나씩 놓되, 이전 행의 퀸들과 충돌하지 않는 열을 골라야 한다.

상태 설계

• 선택 단위 : 각 행에 퀸을 어느 열에 놓을 것인가
• 상태 : queens[i] = i번째 행의 퀸이 놓인 열 번호
• 유망 조건 : 같은 열에 없고, 같은 대각선에 없어야 함

4-Queens 탐색 과정

4×4 체스판에서 탐색이 어떻게 진행되는지 보자.

0행 0열부터 시작했는데, 깊이 들어갈수록 놓을 자리가 없어져서 되돌아오고, 결국 0행 1열부터 다시 시도해서 답을 찾는다. 이 "되돌아오는" 과정이 바로 백트래킹이다.

Java 코드

static int N;
static int[] queens;
static int count = 0;

static void solve(int row) {
    if (row == N) {
        count++;
        return;
    }

    for (int col = 0; col < N; col++) {
        if (!isPromising(row, col)) continue;

        queens[row] = col;
        solve(row + 1);
        queens[row] = -1;
    }
}

static boolean isPromising(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;
}

• queens[row] = col — 선택 (상태 변경)
• solve(row + 1) — 다음 단계로 재귀
• queens[row] = -1 — 되돌리기 (상태 복구)
• isPromising — 같은 열(queens[i] == col)과 대각선(|열 차이| == |행 차이|)을 검사

자주 하는 실수

되돌리기를 빠뜨리는 경우

가장 흔한 실수다. 상태를 변경하고 재귀 호출한 뒤, 복구를 안 하면 다음 선택지를 시도할 때 이전 선택의 흔적이 남는다.

// 잘못된 코드
visited[i] = true;
backtrack(depth + 1);
// visited[i] = false;  ← 이걸 빼먹으면 버그

유망성 검사를 너무 늦게 하는 경우

선택을 한 뒤에 유망성을 검사하면, 이미 불필요한 재귀 호출이 일어난 뒤다. 선택 전에 검사해야 가지치기 효과가 있다.

// 비효율적 — 일단 들어가고 나서 판단
backtrack(depth + 1);
if (!isValid()) return;

// 효율적 — 들어가기 전에 판단
if (!isPromising(choice)) continue;
backtrack(depth + 1);

정리

다음 문서에서는 가지치기 전략을 어떻게 설계하는지, 그리고 백트래킹의 시간복잡도를 어떻게 판단하는지를 다룬다.