백트래킹 알고리즘

개요

백트래킹은 모든 가능한 경우를 탐색하되, 유망하지 않은 경로(promising check)를 조기에 포기해 탐색 공간을 줄이는 기법입니다. 완전 탐색(brute force)과 달리, 불가능한 부분 해를 만나면 즉시 되돌아가(backtrack) 다른 경로를 시도합니다.

상태 공간 트리:
         root
        / | \
       A  B  C
      /|   \
     D E    F    ← D가 유망하지 않으면 가지치기 → E 시도

---

기본 템플릿

void backtrack(상태& state, 결과& result) {
    if (목표 달성) {
        result에 state 추가;
        return;
    }

    for (각 선택지 choice : 가능한 선택들) {
        if (!isPromising(state, choice)) continue; // 가지치기

        state에 choice 적용;    // 선택
        backtrack(state, result); // 재귀
        state에서 choice 제거;  // 선택 취소 (backtrack)
    }
}

---

문제 1: N-Queens

N×N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제입니다.

#include <vector>
#include <iostream>
using namespace std;

class NQueens {
    int n;
    vector<int> col;      // col[row] = 퀸이 놓인 열
    vector<bool> usedCol, usedDiag1, usedDiag2;
    int solutions = 0;

public:
    explicit NQueens(int n) : n(n),
        usedCol(n, false),
        usedDiag1(2*n-1, false),  // row - col + n - 1
        usedDiag2(2*n-1, false)   // row + col
    {}

    void solve(int row = 0) {
        if (row == n) {
            ++solutions;
            return;
        }

        for (int c = 0; c < n; ++c) {
            int d1 = row - c + n - 1;
            int d2 = row + c;

            // 가지치기: 같은 열, 대각선 충돌 체크
            if (usedCol[c] || usedDiag1[d1] || usedDiag2[d2])
                continue;

            // 선택
            usedCol[c] = usedDiag1[d1] = usedDiag2[d2] = true;
            col.push_back(c);

            solve(row + 1);

            // 선택 취소
            usedCol[c] = usedDiag1[d1] = usedDiag2[d2] = false;
            col.pop_back();
        }
    }

    int getSolutions() const { return solutions; }
};

int main() {
    NQueens nq(8);
    nq.solve();
    cout << "8-Queens 해의 수: " << nq.getSolutions() << "\n"; // 92
}

시간복잡도: 가지치기 없이는 O(N!), 가지치기 후 실질적으로 훨씬 감소합니다.

---

문제 2: 순열 생성

#include <vector>
#include <algorithm>
using namespace std;

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == (int)nums.size()) {
        result.push_back(nums);
        return;
    }

    for (int i = start; i < (int)nums.size(); ++i) {
        swap(nums[start], nums[i]);   // 선택
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);   // 취소
    }
}

// 중복 요소가 있는 순열
void permuteUnique(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == (int)nums.size()) {
        result.push_back(nums);
        return;
    }

    set<int> used; // 같은 레벨에서 동일 값 중복 방지
    for (int i = start; i < (int)nums.size(); ++i) {
        if (used.count(nums[i])) continue; // 가지치기
        used.insert(nums[i]);
        swap(nums[start], nums[i]);
        permuteUnique(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

---

문제 3: 조합

// n개 중 k개 선택
void combine(int n, int k, int start,
             vector<int>& current, vector<vector<int>>& result) {
    if ((int)current.size() == k) {
        result.push_back(current);
        return;
    }

    // 가지치기: 남은 원소가 부족하면 중단
    int remaining = n - start + 1;
    int needed    = k - (int)current.size();
    if (remaining < needed) return;

    for (int i = start; i <= n; ++i) {
        current.push_back(i);
        combine(n, k, i + 1, current, result);
        current.pop_back();
    }
}

// 사용
vector<vector<int>> result;
vector<int> current;
combine(5, 3, 1, current, result); // C(5,3) = 10가지

---

문제 4: 부분 집합 합 (Subset Sum)

// 목표 합계를 만드는 부분 집합 탐색
bool subsetSum(const vector<int>& nums, int target,
               int idx, int current, vector<int>& chosen) {
    if (current == target) return true;
    if (idx == (int)nums.size() || current > target) return false;

    // 선택
    chosen.push_back(nums[idx]);
    if (subsetSum(nums, target, idx + 1, current + nums[idx], chosen))
        return true;
    chosen.pop_back();

    // 미선택
    if (subsetSum(nums, target, idx + 1, current, chosen))
        return true;

    return false;
}

---

문제 5: 스도쿠 풀기

#include <array>
using namespace std;

class Sudoku {
    array<array<int,9>, 9> board;

    bool isValid(int row, int col, int num) {
        // 행 체크
        for (int c = 0; c < 9; ++c)
            if (board[row][c] == num) return false;
        // 열 체크
        for (int r = 0; r < 9; ++r)
            if (board[r][col] == num) return false;
        // 3x3 박스 체크
        int br = (row / 3) * 3, bc = (col / 3) * 3;
        for (int r = br; r < br + 3; ++r)
            for (int c = bc; c < bc + 3; ++c)
                if (board[r][c] == num) return false;
        return true;
    }

public:
    bool solve() {
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] != 0) continue; // 이미 채워진 칸

                for (int num = 1; num <= 9; ++num) {
                    if (!isValid(r, c, num)) continue; // 가지치기

                    board[r][c] = num;             // 선택
                    if (solve()) return true;
                    board[r][c] = 0;               // 취소
                }
                return false; // 어떤 숫자도 안 되면 실패
            }
        }
        return true; // 모든 칸 채움
    }
};

---

가지치기 전략

전략	설명	효과
Forward Checking	선택 후 남은 선택지 미리 체크	초기 단계 컷
Arc Consistency	제약 전파 (CSP)	강력한 필터링
Symmetry Breaking	대칭 해를 하나로 통합	해 공간 절반 이상 감소
Minimum Remaining Values	가장 선택지가 적은 변수부터	실패 조기 감지
오름차순 정렬 + 조기 종료	정렬 후 합 초과 시 break	부분합 문제에 유효

---

백트래킹 vs 동적 프로그래밍

항목	백트래킹	동적 프로그래밍
문제 유형	탐색, 열거	최적화, 카운팅
중복 부분 문제	처리 안 함	메모이제이션
공간 복잡도	재귀 깊이 O(n)	O(n²) 이상
가지치기	핵심 최적화	없음

---

핵심 요약

1. 선택 → 재귀 → 취소 패턴을 일관되게 적용
2. isPromising 체크로 유망하지 않은 경로 조기 차단
3. 방문 여부, 사용 여부를 bool 배열로 O(1) 관리
4. 중복 요소가 있는 경우 정렬 후 set 또는 prev 비교로 중복 제거
5. 제약 조건이 많을수록 가지치기 효과가 극대화됨