17. 백트래킹

백트래킹

빠른 설명

백트래킹은 가능한 선택을 하나씩 해 보다가 조건에 맞지 않으면 되돌아가는 탐색이다. 완전탐색이지만 불필요한 가지를 일찍 버리는 것이 핵심이다.

언제 쓰는가

• 순열, 조합 생성
• N-Queen
• 부분집합 탐색
• 조건을 만족하는 배치 찾기

시간복잡도

• 문제마다 다르지만 최악의 경우 지수 시간인 경우가 많다.
• 가지치기를 잘하면 실제 탐색량을 크게 줄일 수 있다.

참고자료

• Wikipedia - Backtracking
• GeeksforGeeks - Backtracking Algorithms
• USACO Guide - Complete Search with Recursion

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int n = 3;
vector<int> chosen;
vector<bool> used;
 
void backtrack() {
    if ((int)chosen.size() == n) {
        for (int x : chosen) cout << x << ' ';
        cout << '\n';
        return;
    }
 
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true;
        chosen.push_back(i);
        backtrack();
        chosen.pop_back();
        used[i] = false;
    }
}
 
int main() {
    used.assign(n + 1, false);
    backtrack();
}

Python 코드

n = 3
chosen = []
used = [False] * (n + 1)
 
def backtrack():
    if len(chosen) == n:
        print(chosen)
        return
 
    for i in range(1, n + 1):
        if used[i]:
            continue
        used[i] = True
        chosen.append(i)
        backtrack()
        chosen.pop()
        used[i] = False
 
backtrack()