백트래킹

수치해석 소프트웨어 마지막 수정: 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%에서 멈춰 있는 솔버 앞에서 이 차이는 아무 위로가 되지 않는다. ↩

이 문서가 문제를 푸는 데 도움이 됐나요? 한 번의 클릭이 다음 검수 순서를 정합니다.

의견을 반영할게요. 감사합니다.

다음으로 읽기 분지한정법 약 5분 더 탐색 →