백트래킹

백트래킹이란?

백트래킹(backtracking) 은 가능한 답을 하나씩 만들어 가다가, 더 진행해도
답이 될 수 없다고 판단되면 즉시 되돌아와(back-track) 다른 선택을 시도하는
탐색 기법입니다. 한마디로 가지치기(pruning)가 들어간 완전 탐색입니다.

미로에서 막다른 길을 만나면 마지막 갈림길로 돌아가 다른 길을 택하는 것과
같습니다.

1. 완전 탐색과 무엇이 다른가

순수 완전 탐색은 모든 후보를 끝까지 다 만들어 봅니다. 백트래킹은 만드는 도중에
"이 선택은 규칙을 어긴다"고 알면 그 가지를 통째로 잘라 냅니다.

N-Queen: 같은 열/대각선에 퀸이 있으면 더 놓아 볼 필요 없이 되돌아간다.

이 가지치기 덕분에 이론상 \(N!\)인 탐색이 실제로는 훨씬 적은 경우만 보고 끝납니다.

2. 백트래킹의 3요소

모든 백트래킹은 다음 세 가지로 구성됩니다.

• 선택(choice): 현재 단계에서 시도할 수 있는 후보들.
• 제약(constraint): 만족해야 하는 규칙 — 어기면 가지치기.
• 목표(goal): 답이 완성되는 조건 — 도달하면 기록.

재귀로 한 단계 내려가며 선택하고, 막히면 선택을 취소(되돌리기)하고 다음 후보를
시도합니다.

3. 상태 공간 트리

백트래킹은 상태 공간 트리를 깊이 우선으로 탐색하는 것과 같습니다.

            (시작)
          /   |   \
        선택A 선택B 선택C
        / \         (제약 위반 → 가지치기)
      ...  ...

각 노드는 "부분적으로 만들어진 답"이고, 잎(leaf)에 도달하면 완성된 답입니다.
중간에 제약을 어기는 노드는 그 아래를 통째로 자릅니다.

4. 대표 문제들

5. 가지치기가 전부다

백트래킹의 성능은 얼마나 빨리, 많이 가지치기하느냐로 결정됩니다. 좋은
가지치기 아이디어:

• 제약 위반 즉시 중단 — 규칙을 어기는 순간 되돌아간다.
• 하한/상한 추정 — "남은 걸 다 더해도 목표에 못 미친다"면 포기.
• 유망성 판단 — 현재까지의 부분 답이 최선의 답을 갱신할 가능성이 없으면 중단.

가지치기 없는 백트래킹은 그냥 느린 완전 탐색입니다.

정리

백트래킹 = 완전 탐색 + 되돌리기 + 가지치기. 선택·제약·목표를 정의하고, 재귀로
내려가며 막히면 되돌아옵니다. 다음 강의에서 표준 구현 골격과 N-Queen, 순열
생성을 코드로 만듭니다.

백트래킹을 코드로

백트래킹은 거의 항상 같은 재귀 골격을 따릅니다. 그 틀을 익히고 대표 문제에
적용합니다.

1. 표준 골격

void backtrack(상태) {
    if (목표 도달) { 답 기록; return; }
    for (각 선택지 c) {
        if (!유효(c)) continue;     // 제약 위반 → 가지치기
        선택(c);                    // 상태에 c 반영
        backtrack(다음 상태);
        선택취소(c);                // 되돌리기 (중요!)
    }
}

선택취소(되돌리기) 가 백트래킹의 심장입니다. 다음 후보를 깨끗한 상태에서
시도하려면 방금 한 선택을 반드시 원래대로 돌려놓아야 합니다.

2. 순열 생성 (N개를 줄 세우기)

int n, perm[10];
bool used[10];
void rec(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; i++) cout << perm[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;       // 이미 쓴 수는 건너뜀
        used[i] = true;              // 선택
        perm[depth] = i;
        rec(depth + 1);
        used[i] = false;             // 선택취소
    }
}

def rec(depth, perm, used, n):
    if depth == n:
        print(*perm)
        return
    for i in range(1, n + 1):
        if used[i]:
            continue
        used[i] = True               # 선택
        perm.append(i)
        rec(depth + 1, perm, used, n)
        perm.pop()                   # 선택취소
        used[i] = False

3. N-Queen (가지치기의 정수)

\(N \times N\) 체스판에 서로 공격하지 못하게 퀸 \(N\)개를 놓는 방법의 수.

int n, cnt = 0;
int col[15];                         // col[r] = r행 퀸의 열
bool ok(int r, int c) {
    for (int i = 0; i < r; i++) {
        if (col[i] == c) return false;            // 같은 열
        if (abs(col[i] - c) == abs(i - r)) return false;  // 대각선
    }
    return true;
}
void solve(int r) {
    if (r == n) { cnt++; return; }   // 모든 행에 다 놓음
    for (int c = 0; c < n; c++) {
        if (!ok(r, c)) continue;     // 공격받으면 가지치기
        col[r] = c;                  // 선택
        solve(r + 1);
        // 배열 덮어쓰기라 별도 선택취소 불필요
    }
}

행마다 퀸 하나씩만 놓는 것으로 탐색 공간을 \(N^N\)에서 \(N!\)로 줄이고, ok의
가지치기로 실제 탐색량을 더 크게 줄입니다.

4. 부분집합 합 (가지치기 예)

bool rec(int idx, int sum, int target) {
    if (sum == target) return true;
    if (idx == n || sum > target) return false;   // 초과하면 가지치기
    if (rec(idx + 1, sum + a[idx], target)) return true;  // 포함
    return rec(idx + 1, sum, target);              // 미포함
}

sum > target이면 더 진행할 필요 없이 즉시 중단하는 것이 가지치기입니다.

5. 흔한 실수

• 선택취소 누락 — 되돌리기를 빠뜨리면 상태가 오염되어 답이 틀립니다.
  (단, 배열을 통째로 덮어쓰는 경우는 예외.)
• 가지치기 부재 — 제약 검사를 안 하면 그냥 느린 완전 탐색이 됩니다.
• used 배열 안 씀 — 순열에서 중복 사용 방지를 빠뜨림.
• 파이썬 깊이/속도 — 깊은 백트래킹은 setrecursionlimit와 효율적 가지치기 필수.

6. 패턴 알아보기

• "가능한 모든 경우를 나열/세라" + 제약이 있다 → 백트래킹.
• "조건을 만족하는 배치/조합/순열" → 백트래킹.
• \(N\)이 작고(\(\le 15\) 부근) 완전 탐색이지만 제약으로 가지치기가 가능 → 백트래킹.

실전에서 백트래킹 문제 알아보기

백트래킹 문제는 골격이 거의 같아서, 승부는 상태 설계와 가지치기에서
갈립니다. 실수 없이 골격을 찍어 내는 절차를 정리합니다.

1. 출제 신호

• "조건을 만족하는 모든 수열을 사전순으로 출력" — N과 M 시리즈류.
  생성 + 제약이면 백트래킹입니다.
• 배치 문제 — N-Queen, 스도쿠, 알파벳 격자 탐험처럼 "서로 공격하지 않게 /
  겹치지 않게 놓기".
• \(N \le 15\) 안팎인데 단순 \(2^N\)/\(N!\) 완전 탐색은 살짝 빡빡 — 가지치기로
  깎으라는 신호입니다.
• 부분 수열의 합·조합이 조건을 일찍 위반하면 더 볼 필요가 없는 구조.

2. 풀이 결정 절차

1. 상태를 정합니다 — 지금까지 고른 것(경로)과, 유망성 검사를 \(O(1)\)로
   만들어 줄 보조 표시(열 사용 여부, 대각선 사용 여부 등).
2. 선택지를 나열하는 순서를 정합니다 — 사전순 출력이 요구되면 선택지를
   정렬된 순서로 순회해야 합니다.
3. 가지치기 조건을 적습니다 — "여기서 이미 합이 목표를 넘으면 중단"처럼,
   재귀 호출 전에 검사할 수 있는 형태로.
4. 표시 → 재귀 → 해제가 짝을 이루는지 골격에서 확인합니다.

3. 자주 하는 실수

• 방문 해제 누락. 표시만 하고 해제를 잊으면 두 번째 가지부터 후보가
  사라집니다. 표시와 해제는 같은 들여쓰기 깊이에서 짝으로 쓰세요.

void rec(int depth) {
    if (depth == m) { print(); return; }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;       // 유망성 검사는 호출 "전"에
        used[i] = true;              // 1) 표시
        path[depth] = a[i];
        rec(depth + 1);              // 2) 재귀
        used[i] = false;             // 3) 해제 — 표시와 반드시 짝!
    }
}

• N-Queen에서 격자 전체 검사. 매번 보드를 훑으면 너무 느립니다. 열,
  두 대각선(r+c, r-c+N)의 사용 여부 배열로 \(O(1)\) 검사가 정석입니다.
• 중복 값 처리. 같은 숫자가 여러 개인 입력에서 "같은 수열 중복 출력"을
  막으려면 정렬 후 i > start && a[i] == a[i-1]인 후보를 건너뜁니다.
• 가지치기를 기저에서 함. 끝까지 내려간 뒤 검사하면 가지치기 효과가
  없습니다. 위반은 가능한 한 위쪽(호출 전) 에서 잘라야 합니다.
• 전역 경로에 push 후 pop 누락. vector에 push_back했으면 재귀 후
  pop_back. 비대칭이면 경로가 오염됩니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것 → 어려운 것 순서입니다. 순열·조합
생성형(N과 M류)으로 골격을 손에 익힌 뒤 N-Queen형 배치 문제로 가세요.

같은 골격을 안 보고 5분 안에 쓸 수 있을 때까지 반복하는 것이 이 단원의
핵심 훈련입니다. 3문제 이상 풀어 클리어하면 레이팅의 CLASS 보너스에
반영됩니다.