백트래킹

수치해석 소프트웨어 마지막 수정: 2026-08-31 04:27:41

1. 개요[편집]

백트래킹 Backtracking
정체	해공간 트리 위의 깊이 우선 탐색 + 가지치기
목적	충족(feasibility) — 최적화는 분지한정법
메모리	$O(n)$ — 현재 경로만 들고 있으면 된다
최악 시간	지수 — 가지치기가 전부다
가지치기 도구	전방검사 · 호 일관성(AC-3) · 노굿
순서화 휴리스틱	MRV · degree · LCV
대표 사례	n-퀸 · 스도쿠 · 부분집합합 · 그래프 색칠 · DPLL

“다 해보긴 해야 하는데, 다 해보면 죽는다”에 대한 첫 번째 대답.

백트래킹(backtracking)은 부분해를 한 변수씩 확장해 나가다가 그 부분해가 제약을 위반하는 순간 더 내려가지 않고 직전 분기점으로 되돌아가는 체계적 완전탐색 기법이다. 핵심은 “체계적”과 “완전”이라는 두 단어에 있다 — 해를 절대로 빠뜨리지 않으면서(완전), 같은 해를 두 번 세지 않고(체계적), 그러면서도 명백히 가망 없는 부분트리는 아예 만들지도 않는다.

기계적으로 보면 이건 깊이 우선 탐색이다. 다만 그래프가 미리 존재하지 않고 탐색하면서 생성된다는 점이 다르다. 정점은 ” $x_1=3, x_2=7$ 까지 정한 부분해” 같은 상태이고, 간선은 “다음 변수에 값 하나를 할당”이다. DFS 를 쓰는 이유도 명확하다 — 메모리가 현재 경로 길이에만 비례한다. 같은 해공간을 너비 우선 탐색으로 훑으면 프런티어가 $b^d$ 로 부풀어 답을 보기 전에 메모리부터 터진다.

이름은 1950년대에 D. H. 레머가 붙였다고 전해지지만, 절차 자체는 훨씬 오래됐다. 미로를 실 풀며 들어갔다가 되감아 나오는 것, 스도쿠를 연필로 풀다가 지우개를 쓰는 것 전부 백트래킹이다.

2. 골격과 가지치기[편집]

변수 $x_1,\dots,x_n$ 이 각각 정의역 $D_1,\dots,D_n$ 을 갖고, 제약 집합 $C$ 를 모두 만족하는 할당을 찾는다고 하자. 이게 곧 제약 충족 문제(CSP)의 정의다.

solve(k):
    if k > n: 해 하나 출력; return
    for v in D_k:
        if 부분해 (x_1..x_{k-1}, x_k=v) 가 제약을 위반하지 않으면:
            x_k = v
            solve(k+1)
            x_k = 미할당          # ← 되돌리기(undo)

여기서 되돌리기가 상태를 정확히 원복해야 한다는 것이 첫 번째 구현 함정이다. 값 하나를 되돌리는 것은 쉬운데, 가지치기 과정에서 다른 변수들의 정의역을 깎아 놨다면 그것까지 전부 복원해야 한다. 그래서 실무 코드는 트레일(trail, 변경 로그 스택)을 두고 분기점마다 마크를 찍은 뒤 되돌아갈 때 마크까지 팝한다. 이 구조는 그대로 SAT 풀이기와 제약 프로그래밍 엔진의 심장이다.

가지치기의 강도에 따라 이름이 갈린다.

소박한 생성-검사(generate and test) — 완성된 할당만 검사한다. $\prod|D_i|$ 개를 전부 만든다. 백트래킹이라 부르지도 않는다.
표준 백트래킹 — 부분해가 이미 위반이면 즉시 되돌아간다. 위 코드가 이것.
전방 검사(forward checking) — 값을 할당할 때마다 아직 할당 안 된 변수들의 정의역에서 그 값과 충돌하는 것을 지운다. 어느 미할당 변수의 정의역이 비면 즉시 실패를 선언한다. 실패를 몇 단계 앞당기는 효과가 크다.
호 일관성 전파(arc consistency) — 아래에서 따로.

3. 제약 전파 — AC-3 와 그 친구들[편집]

호 일관성은 이렇게 정의된다. 이항 제약 $C_{ij}$ 에 대해 호 $(x_i, x_j)$ 가 일관적이라는 것은, $D_i$ 의 모든 값 $a$ 에 대해 $(a,b)$ 가 $C_{ij}$ 를 만족하는 $b \in D_j$ 가 적어도 하나 존재한다는 뜻이다. 존재하지 않는 $a$ 는 어떤 해에도 못 들어가므로 지워도 안전하다.

AC-3(Mackworth, 1977)은 이 검사를 큐로 돌린다. 모든 호를 큐에 넣고, 하나 꺼내 $D_i$ 를 깎았으면 $x_i$ 에 걸린 이웃 호들을 다시 큐에 넣는다. 정의역 크기 $d$ , 제약(호) 수 $e$ 일 때 시간은 $O(ed^3)$ , 공간은 $O(e)$ 다.¹ 값 하나당 지지자를 명시적으로 관리하는 AC-4 는 $O(ed^2)$ 로 최악 시간이 최적이지만 상수와 메모리가 커서 실전에서는 AC-3 또는 AC-2001 계열이 더 많이 쓰인다.

전파를 탐색 매 노드마다 돌리는 것을 MAC(maintaining arc consistency)이라 한다. 노드당 비용은 올라가지만 트리 크기가 줄어드는 폭이 대개 더 크다. 물론 항상은 아니다 — 제약이 성긴 문제에서는 전파가 지울 게 없어 순수 오버헤드가 된다. 전파 강도와 노드 수의 트레이드오프를 어디서 끊을 것인가가 이 분야의 영원한 튜닝 포인트다.

호 일관성은 해의 존재를 보장하지 않는다는 점을 잊으면 안 된다. 모든 호가 일관적이어도 해가 없을 수 있다(삼각형 그래프의 2-색칠). 반대로 제약 그래프가 트리면 호 일관성만으로 백트래킹 없이 해를 뽑을 수 있다는 좋은 소식도 있다.

4. 순서화 휴리스틱 — 어느 변수를 먼저 정할 것인가[편집]

가지치기만큼, 아니 그 이상으로 효과가 큰 것이 순서다.

MRV(minimum remaining values, 최소잔여값). 남은 정의역이 가장 작은 변수를 다음에 고른다. fail-first 원칙이라고도 부르는데, 이름이 성격을 다 설명한다 — 어차피 실패할 거면 트리 위쪽에서 빨리 실패해야 잘려 나가는 부분트리가 크다. 실패를 미루면 실패의 사본을 지수 개 만들게 된다. 그래프 색칠의 DSATUR 이 “포화도가 가장 높은 정점부터”를 쓰는 것이 정확히 이 원리의 특수 사례다.

degree 휴리스틱. MRV 동점일 때(특히 탐색 시작 시점엔 전부 동점이다) 미할당 변수와 제약을 가장 많이 공유하는 변수를 고른다. 제약 그래프에서 차수가 큰 놈부터 잡아 그래프를 빨리 쪼개자는 것.

LCV(least constraining value, 최소 제약 값). 값 순서는 반대 방향이다. 이웃 정의역을 가장 적게 깎는 값부터 시도한다. 어차피 해 하나만 찾으면 되는 문제에서는 살아남을 확률이 높은 쪽부터 보는 게 이득이기 때문. 변수는 실패할 것 같은 쪽부터, 값은 성공할 것 같은 쪽부터 — 방향이 반대라는 게 헷갈리지만 목적을 생각하면 둘 다 자연스럽다. 모든 해를 열거하는 문제라면 LCV 는 의미가 없어진다.

5. 되돌아가는 방식들[편집]

기본형은 시간순 백트래킹(chronological backtracking)이다. 막히면 무조건 직전 분기점으로 되돌아간다. 문제는 실패의 원인이 훨씬 위쪽 변수일 때다. 원인과 무관한 아래쪽 변수들의 조합을 전부 다시 시도하면서 같은 실패를 지수 번 반복하는 것을 쓸모없는 반복(thrashing)이라 부른다.

백점핑(Gaschnig, 1979) — 실패한 변수와 실제로 충돌한 가장 얕은 변수까지 한 번에 뛰어올라간다.
충돌 지향 백점핑(Prosser, 1993) — 변수마다 충돌 집합(conflict set)을 유지하며 점프하고, 점프하면서 충돌 집합을 병합해 전파한다.
의존성 지향 백트래킹(Stallman & Sussman, 1977) — 실패의 원인 조합을 노굿(nogood)으로 기록해 두었다가 이후 탐색에서 재사용한다. 여기서 학습(learning)이라는 개념이 처음 나왔다.

노굿 학습을 절 형태로 바꾸고, 학습한 절로 되돌아갈 지점을 정하고, 여기에 재시작과 활동도 기반 변수 순서를 얹은 것이 현대 SAT 의 CDCL이다. 즉 CDCL 은 백트래킹의 직계 후손이며, “시간순으로 되돌아간다”는 원조의 마지막 성질까지 버린 판이다. 자세한 것은 SAT 풀이기 문서로 넘긴다.

반복 깊이증가(iterative deepening, IDDFS)는 결이 다른 변형이다. 깊이 한계를 $1,2,3,\dots$ 로 올리며 깊이 제한 DFS 를 반복한다. 같은 노드를 여러 번 방문하지만, 분기 계수 $b>1$ 인 트리에서 마지막 레벨이 전체의 상수 비율을 차지하므로 총 노드 수는 $b^d \cdot \frac{b}{b-1}$ 정도, 즉 상수 배 오버헤드로 끝난다. 대가로 BFS 의 최단해 보장을 $O(d)$ 메모리에 얻는다. 여기에 허용적 휴리스틱을 얹어 깊이 대신 $f=g+h$ 한계를 올리는 것이 IDA*(Korf, 1985)이고, 메모리가 빠듯한 퍼즐 탐색의 국룰이다.

6. 교과서 사례가 교과서인 이유[편집]

n-퀸. 변수는 열, 값은 행, 제약은 행·두 대각선 불충돌. 대각선 충돌은 $i-j$ 와 $i+j$ 가 같은지로 판정되므로 비트마스크 세 개면 $O(1)$ 검사가 된다. $n=8$ 의 해는 92개(대칭을 제하면 12개). 참고로 아무 해나 하나 찾는 것이라면 백트래킹이 필요 없다 — 명시적 구성 공식이 알려져 있다. 이 문제가 유명한 것은 어렵기 때문이 아니라 가지치기의 효과를 눈으로 세기 좋기 때문이다.
스도쿠. 변수 81개, 정의역 9개, 제약은 행·열·박스의 all-different. 전방검사 + MRV 만 얹으면 사람이 어렵다고 하는 문제도 노드 몇 백 개에서 끝난다. 여기에 “어떤 칸이 한 숫자만 남았다”, “어떤 숫자가 한 칸에만 들어갈 수 있다” 같은 전파 규칙을 더하면 대부분 탐색 없이 풀린다. 일반화된 $n^2 \times n^2$ 스도쿠의 완성 가능성 판정은 NP-완전이다.
부분집합합. $n$ 개 수에서 합이 $T$ 인 부분집합. 정렬 후 “남은 것을 다 더해도 $T$ 에 못 미친다”, “지금 합이 이미 $T$ 를 넘었다”(양수인 경우) 두 가지 상계·하계 가지치기가 표준이다. 완전탐색 $2^n$ 은 반씩 나눠 만나기(meet in the middle, Horowitz–Sahni 1974)로 $O(2^{n/2})$ 까지 떨어지는데, 이건 백트래킹이 아니라 분할 정복의 아이디어라는 점이 재미있다. 최적화판인 배낭 문제로 넘어가면 도구가 동적 계획법과 분지한정법으로 갈린다.
그래프 색칠. $k$ -색칠 가능성 판정은 전형적인 CSP다. 백트래킹으로 정확해를 구하는 것은 소규모에서만 현실적이고, 실무는 그래프 색칠 문서가 다루는 탐욕 휴리스틱에 맡긴다.

7. 충족이냐 최적화냐 — 분지한정법과의 선[편집]

둘 다 해공간 트리를 DFS 로 훑으며 가지를 자르지만 자르는 근거가 다르다.

	백트래킹	분지한정법
목적	해가 있는가 / 해를 열거	최적해와 그 최적성 증명
가지치기 근거	제약 위반 — 논리적 불가능	완화 경계가 인커번트보다 나쁨
필요한 부품	제약 검사, 전파	완화 문제, 인커번트
탐색 순서	대개 DFS(메모리)	최적 우선·최선 경계도 흔함
조기 종료	첫 해에서 멈춤	갭이 0 이 될 때까지

한 문장으로 줄이면 백트래킹은 “안 되는 이유”로 자르고, 분지한정법은 “더 나을 수 없는 이유”로 자른다. 그래서 최적화 문제에 백트래킹만 쓰면 모든 실행가능해를 다 세게 되고, 충족 문제에 분지한정법을 쓰면 쓸 경계가 없어 그냥 백트래킹으로 퇴화한다. 둘을 섞은 형태도 흔하다 — 목적함수 상한을 하나의 제약으로 취급해 CSP 로 넣고, 해를 찾을 때마다 그 제약을 조여 다시 푸는 방식이다.

8. 시뮬레이션 쪽에서 만나는 자리[편집]

정확 커버와 조합 배치. 크누스의 알고리즘 X 를 댄싱 링크(DLX)라는 이중 연결 리스트 트릭으로 구현하면, 되돌리기가 포인터 네 개 복원으로 끝나 백트래킹의 undo 비용이 거의 사라진다. 폴리오미노 타일링, 격자 패턴 배치, 실험 설계의 조합 생성에 그대로 쓰인다.
분자 배좌 탐색. 회전 가능 결합의 이면각을 이산화하고 원자 간 겹침을 제약으로 두면 분자동역학 이전 단계인 배좌 열거가 CSP가 된다. 단백질 곁사슬 배치의 dead-end elimination 은 “이 회전이성체는 어떤 최적해에도 못 들어간다”를 증명해 정의역을 깎는 것으로, 이름만 다를 뿐 제약 전파다.
조립 순서·공정 스케줄링. 선후 관계와 자원 제약이 걸린 순서 결정은 CSP 로 모델링하고 백트래킹 + 전파로 푸는 것이 표준이다. 상용 제약 프로그래밍 솔버가 이 시장에서 정수계획법과 경쟁한다.
모델 검증과 코드 생성. SAT 풀이기·SMT 위에 올라간 검증 도구는 전부 이 골격이다. 시뮬레이션 코드를 짜는 쪽이 아니라 그 코드가 맞는지 따지는 쪽에서 백트래킹이 돈다.

한 가지 현실적인 조언. 백트래킹은 잘 돌 때는 마법처럼 빠르고 안 될 때는 우주가 끝날 때까지 안 끝난다. 노드 수 카운터와 시간 제한을 처음부터 박아 두고, 제한에 걸리면 담금질 모사나 지역 탐색 같은 불완전 방법으로 넘어가는 이중 전략을 준비하는 것이 정신 건강에 좋다.² 완전성은 공짜가 아니다.³

9. 관련 문서[편집]

지수 3 의 출처가 헷갈리기 쉽다. 호 하나를 한 번 검사(revise)하는 데 두 정의역의 곱만큼 걸려 $O(d^2)$ , 그리고 호 $(x_i,x_j)$ 가 큐에 다시 들어가는 것은 $D_j$ 가 실제로 깎였을 때뿐이라 많아야 $d$ 번이다. 호가 $e$ 개니 $O(e \cdot d \cdot d^2) = O(ed^3)$ . 큐에 넣는 조건을 “깎였을 때만”으로 안 걸면 이 논증이 통째로 무너지므로, 구현에서 저 조건문은 최적화가 아니라 복잡도 그 자체다. ↩
실제로 상용 솔버들은 이걸 내장하고 있다. “재시작”이라는 이름으로 트리를 통째로 버리고 처음부터 다시 하는 전략이 CDCL 의 표준 부품이 된 것이, 완전탐색이 확률적 방법의 겉옷을 입은 대표적인 사례다. ↩
그리고 완전탐색이 완전하다는 것과 끝난다는 것은 다른 말이다. 유한 정의역이면 언젠가는 끝나는 것이 수학적으로 보장되지만, 그 “언젠가”가 태양의 수명보다 길면 공학적으로는 안 끝나는 것과 같다. 진행률 표시줄이 3%에서 멈춰 있는 솔버 앞에서 이 차이는 아무 위로가 되지 않는다. ↩