[백트래킹] 3. 실전 패턴과 면접 대비

패턴을 알면 풀이가 보인다

백트래킹 문제는 겉모습이 다양하지만, 내부 구조는 몇 가지 패턴으로 수렴한다. 패턴을 인식하면 "이 문제를 어떻게 백트래킹으로 모델링할까"에 대한 답이 빠르게 나온다.

패턴 1 — 순열

N개 원소를 나열하는 모든 순서를 구하는 유형이다.

• 선택 단위 : 각 위치에 어떤 원소를 놓을 것인가
• 제약 : 이미 사용한 원소는 다시 사용할 수 없다
• 상태 관리 : boolean[] visited 배열

void permutation(int depth) {
    if (depth == N) {
        결과 처리;
        return;
    }

    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;

        visited[i] = true;
        result[depth] = arr[i];
        permutation(depth + 1);
        visited[i] = false;
    }
}

• visited 배열이 "이미 선택했는가"를 추적한다.
• 시간복잡도 : O(N!)

패턴 2 — 조합과 부분집합

N개 원소에서 일부를 뽑는 유형이다. 조합은 정확히 K개를 뽑는 것이고, 부분집합은 0~N개 중 아무 개수나 뽑는 것이다.

• 선택 단위 : 각 원소를 포함할 것인가, 말 것인가
• 제약 : 중복 방지를 위해 이전 인덱스 이후만 탐색
• 핵심 : start 파라미터

조합 (N개 중 K개)

void combination(int start, int depth) {
    if (depth == K) {
        결과 처리;
        return;
    }

    for (int i = start; i < N; i++) {
        result[depth] = arr[i];
        combination(i + 1, depth + 1);
    }
}

• start가 매 재귀마다 증가하므로 이전에 선택한 것보다 뒤의 원소만 고른다.
• 되돌리기가 명시적으로 안 보이지만, result[depth]가 다음 반복에서 덮어쓰이므로 자연스럽게 복구된다.

부분집합 (포함/미포함)

void subset(int index) {
    if (index == N) {
        결과 처리;
        return;
    }

    selected[index] = true;
    subset(index + 1);
    selected[index] = false;
    subset(index + 1);
}

• 각 원소에 대해 "포함한다 / 안 한다" 두 갈래로 나뉜다.
• 트리의 모양이 이진 트리가 된다. 시간복잡도 : O(2^N)

패턴 3 — 2D 격자 배치

2차원 격자 위에 무언가를 배치하거나 덮는 유형이다. N-Queens, 색종이 붙이기 등이 여기에 해당한다.

• 선택 단위 : 격자의 특정 위치에 어떤 것을 놓을 것인가
• 상태 관리 : 2D 배열 자체가 상태
• 되돌리기 : 배열의 영역을 원래 값으로 복구

이 패턴에서 자주 실수하는 부분이 영역 전체를 변경/복구하는 것이다. 이전에 분석한 BOJ17136 실패 코드에서 테두리만 지우고 내부를 안 지운 것이 바로 이 실수다.

// 올바른 영역 변경 — 이중 for문으로 전체 순회
for (int i = r; i < r + size; i++) {
    for (int j = c; j < c + size; j++) {
        grid[i][j] = value;
    }
}

패턴 4 — 그래프 탐색 + 조건

그래프 위에서 특정 조건을 만족하는 경로나 부분 그래프를 찾는 유형이다. 해밀턴 경로, 외판원 순회 등이 대표적이다.

• 선택 단위 : 다음에 방문할 노드
• 제약 : 이미 방문한 노드 재방문 금지, 거리/비용 제한 등
• 상태 관리 : visited 배열 + 현재 비용/거리

이 유형은 보통 N이 작을 때(20 이하) 백트래킹으로 풀 수 있고, N이 크면 DP + 비트마스킹 등 다른 기법이 필요하다.

문제를 만났을 때 접근 순서

새로운 문제를 만났을 때, 아래 순서로 생각하면 빠르게 구조를 잡을 수 있다.

1. 완전탐색이 필요한지 — "모든 경우" "최소" "최대" "가능한지" 같은 키워드가 있으면 완전탐색 계열을 의심
2. N의 크기 확인 — 백트래킹은 N이 작을 때만 유효
3. 패턴 매칭 — 순열/조합/격자/그래프 중 어디에 가까운지 판단
4. 상태 설계 — 선택 단위, 유망 조건, 되돌리기 대상을 결정

면접 Q&A

정리

백트래킹은 결국 세 가지만 잘하면 된다. 상태를 잘 설계하고, 가지를 잘 치고, 되돌리기를 빠뜨리지 않는 것.