백트래킹: 가 보고 막히면 되돌아오기

미로에서 갈림길마다 한쪽을 골라 들어가다가, 막다른 곳에 닿으면 바로 앞 갈림길로 돌아가 다른 쪽을 고릅니다. 이것이 백트래킹입니다. 판에 퀸을 한 줄씩 놓으며 한 걸음씩 따라가 보세요.

한 줄 답. 백트래킹은 고를 것을 하나씩 정해 가다가, 조건이 깨지면 그 가지를 더 내려가지 않고 바로 앞 고름으로 돌아가 다른 것을 고르는 방법입니다. 모든 경우를 다 만들어 본 뒤 검사하는 것보다 훨씬 적게 들릅니다. 그래도 가장 나쁠 때는 여전히 지수로 늘어납니다.

문제: n × n 판에 퀸 n 개를, 어느 두 퀸도 같은 세로줄이나 대각선에 있지 않게 놓습니다(줄마다 하나씩 놓으니 가로줄은 저절로 다릅니다). 「다음」을 누를 때마다 일 하나씩 나아갑니다. 위 줄부터, 왼쪽 칸부터 한 칸씩 봅니다. 위 퀸과 부딪히면 막은 퀸에서 그 칸으로 주황 화살표가 가고(「같은 세로줄」 또는 「대각선」), 그 칸에는 ×(해 봤음)가 남습니다. 부딪히지 않으면 초록 퀸을 놓습니다(「놓음」). 줄의 모든 칸에 × 가 있으면 막힘: 파란 굽은 화살표를 따라 윗줄로 되돌아가 그 퀸을 들어내고(주황 점선, 「되돌아감」), 다음 걸음에 그 퀸을 오른쪽 다음 칸으로 옮겨(파란 점선, 「다음 칸」) 거기부터 다시 봅니다. 떠난 자리는 흐린 점선으로 남습니다. 파란 줄은 지금 다루는 줄이고, 한 줄을 새로 시작하면 그 줄의 × 는 지워집니다.

해 볼 것. ① n = 4 는 33걸음 만에 첫 답에 닿습니다. 칸을 26번 놓아 보고, 그중 놓음이 8번, 되돌아감이 4번입니다. 첫 답은 줄마다 2, 4, 1, 3 칸입니다. ② n = 5 는 되돌아가지 않고 15걸음 만에, n = 7 은 46걸음 만에 끝납니다. n = 6 은 217걸음(되돌아감 25번)이 걸립니다. 판이 크다고 늘 오래 걸리지는 않습니다. ③ n = 8 에서 「첫 답까지」를 누르면 1,071걸음(놓아 본 칸 876번, 놓음 113번, 되돌아감 105번)이고, 첫 답은 1, 5, 8, 6, 3, 7, 2, 4 칸입니다.

1. 생각: 고를 것의 트리를 깊이 우선으로, 틀린 가지는 버리고

N-퀸 문제(N-Queens problem)를 「1줄의 칸을 고른다 → 2줄의 칸을 고른다 → …」처럼 고를 것 n 개를 차례로 정하는 일로 봅니다. 빈 판에서 시작해 1줄의 칸 n 가지로 갈라지고, 그 하나하나가 다시 2줄의 칸 n 가지로 갈라집니다. 이렇게 그리면 상태 공간 트리(state space tree)가 됩니다. 맨 위(루트)는 빈 판, 노드(node) 하나는 「위에서 몇 줄까지 퀸을 놓은 상태」, 맨 아래(리프)는 n 줄을 다 놓은 배치입니다.

백트래킹은 이 트리를 깊이 우선으로 돕니다. 한 가지를 골라 끝까지 내려가 보고, 더 갈 수 없으면 바로 위 노드로 올라와 다음 가지로 내려갑니다. 여기에 하나를 더합니다. 노드에 들를 때마다 조건을 검사해서, 이미 틀린 노드 아래로는 내려가지 않습니다. 2줄까지 놓았는데 두 퀸이 대각선에 있으면, 3줄부터 n 줄까지 무엇을 놓아도 답이 될 수 없으니 그 아래 가지 전체를 통째로 버립니다. 이것을 가지치기라고 부릅니다.

트리는 미리 만들어 두지 않습니다. 고른 것을 목록 끝에 하나 더하면 자식 노드로 내려간 것이고, 목록 끝에서 하나 빼면 부모 노드로 올라온 것입니다. 그래서 메모리는 지금 내려온 길 하나(목록 하나)만 듭니다.

깊이 우선 탐색과의 관계

너비 우선·깊이 우선 탐색 쪽의 깊이 우선 탐색은 이미 있는 그래프를 돌고, 같은 곳을 두 번 들르지 않게 「들렀음」을 표시해 둡니다. 백트래킹이 도는 것은 고를 것의 트리입니다. 길마다 고른 것이 달라 같은 노드를 두 번 만나지 않으니 들렀음 표시가 필요 없고, 대신 올라올 때 고른 것을 되돌립니다(목록에서 빼기). 도는 순서는 같고, 「검사해서 버리기」와 「되돌리기」가 더해진 것이 백트래킹입니다.

2. 손으로 따라가기: n = 4

실험 ① 의 처음 판(n = 4)을 끝까지 따라갑니다. 칸은 왼쪽부터 1, 2, 3, 4 입니다. 「놓인 퀸」은 그 걸음이 끝난 뒤 1줄부터 차례로 놓인 칸입니다. 실험은 칸 하나를 볼 때, 되돌아갈 때, 다음 칸으로 옮길 때마다 한 걸음씩 가므로, 표의 한 줄은 실험의 여러 걸음을 묶은 것입니다.

실험의 걸음한 일건너뛴 칸(까닭)놓인 퀸
1놓음: 1줄 1칸(위에 퀸이 없어 부딪힐 것이 없다)없음1
2–4놓음: 2줄 3칸(부딪히지 않는 첫 칸)1(세로줄), 2(대각선)1, 3
5–9막힘: 3줄에 놓을 곳이 없다. 2줄의 퀸(3칸)을 들어낸다1(세로줄), 2(대각선), 3(세로줄), 4(대각선)1
10–11놓음: 2줄 4칸(3칸까지는 해 봤으니 4칸으로 옮겨 보고, 부딪히지 않는다)없음1, 4
12–13놓음: 3줄 2칸(부딪히지 않는 첫 칸)1(세로줄)1, 4, 2
14–18막힘: 4줄에 놓을 곳이 없다. 3줄의 퀸(2칸)을 들어낸다1(세로줄), 2(세로줄), 3(대각선), 4(세로줄)1, 4
19–22막힘: 3줄의 퀸을 3칸으로 옮겨 봤지만 남은 칸도 다 부딪혀 더 놓을 곳이 없다. 2줄의 퀸(4칸)을 들어낸다3(대각선), 4(세로줄)1
23막힘: 2줄에 더 놓을 곳이 없다(4칸이 끝이라 옮길 칸이 없다). 1줄의 퀸(1칸)을 들어낸다없음없음
24–25놓음: 1줄 2칸(1칸은 해 봤으니 2칸으로 옮긴다)없음2
26–29놓음: 2줄 4칸(부딪히지 않는 첫 칸)1(대각선), 2(세로줄), 3(대각선)2, 4
30놓음: 3줄 1칸(부딪히지 않는 첫 칸)없음2, 4, 1
31–33놓음: 4줄 3칸(부딪히지 않는 첫 칸). 퀸 4개를 다 놓았다. 첫 답1(세로줄), 2(세로줄)2, 4, 1, 3

걸음 9, 18, 22, 23 이 되돌아감이고, 바로 뒤의 걸음 10, 19, 24 가 들어낸 퀸을 오른쪽 다음 칸으로 옮깁니다. 걸음 22 에서 들어낸 2줄의 퀸은 끝 칸(4칸)에 있어 옮길 칸이 없으니, 걸음 23 에서 한 줄 더 올라갑니다. 1줄에 1칸을 놓은 가지는 걸음 23 에서 통째로 버려졌고, 그 아래의 배치는 하나도 끝까지 만들어 보지 않았습니다.

1 · 3줄이 다 막힘 2 · 2줄로 되돌아감 3 · 다음 칸(4칸)으로
실험 ① 의 n = 4, 걸음 8 → 9 → 10. 1: 3줄의 네 칸에 모두 ×(해 봤음)가 있어 놓을 곳이 없다. 2: 파란 굽은 화살표를 따라 한 줄 위(2줄)로 되돌아가 3칸의 퀸을 들어낸다(주황 점선). 3: 다음 걸음에 그 퀸을 오른쪽 다음 칸(4칸)으로 옮긴다. 떠난 3칸에는 × 와 흐린 점선이 남고, 3줄은 다시 내려올 때 새로 시작하니 × 를 지운다.

3. 뼈대 코드: 고른다 → 내려간다 → 되돌린다

재귀로 쓰면 「어디로 되돌아갈지」를 함수 호출이 기억해 줍니다. 아래는 n = 8 의 답을 모두 찾습니다.

def solve(n):
    cols, answers = [], []          # cols[r] = r줄에 놓은 퀸의 칸
    def place(row):
        if row == n:                # 다 놓았다: 답 하나
            answers.append(cols.copy())
            return
        for c in range(n):
            if all(c != q and abs(c - q) != row - r for r, q in enumerate(cols)):
                cols.append(c)      # 고른다
                place(row + 1)      # 내려간다
                cols.pop()          # 되돌린다
    place(0)
    return answers

print(len(solve(8)), solve(4))      # 92 [[1, 3, 0, 2], [2, 0, 3, 1]]

Python 은 0 부터 세므로 [1, 3, 0, 2] 는 표의 2, 4, 1, 3 칸입니다. all(...) 이 가지치기입니다. 놓기 전에 위 퀸들과 세로줄(c != q)과 대각선(칸의 차이가 줄의 차이와 같은가)을 검사해, 부딪히면 그 칸 아래로는 내려가지 않습니다. 첫 답만 필요하면 답을 찾은 순간 참을 돌려주고 멈추게 고칩니다.

모든 순서(순열)를 만드는 일은 표준 라이브러리에 있습니다. 안에서 하는 일은 「다 만들기」이고, 도중에 가지를 버리지는 않습니다.

from itertools import permutations
list(permutations("abc"))   # [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

N-퀸 문제에 permutations(range(8)) 을 쓰면 줄마다 다른 칸을 고른 배치만 나와 세로줄은 저절로 겹치지 않습니다. 그래도 40,320 개(8 × 7 × … × 1)를 모두 만든 뒤에 대각선을 검사하니, 다음 절의 「다 놓아 본 뒤 검사」 쪽입니다.

4. 가지치기의 효과

같은 트리를 두 가지로 돌아 봅니다. 다 놓아 본 뒤 검사(완전 탐색, brute force)는 줄마다 n 칸을 모두 골라 nⁿ 개의 배치를 끝까지 만들고 나서 맞는지 봅니다. 놓을 때마다 검사는 위의 뼈대 코드처럼 부딪히는 칸 아래로 내려가지 않습니다. 둘 다 끝까지 돌아 답을 모두 찾고, 들른 노드(빈 판 하나 + 퀸을 놓은 상태 하나하나)를 셉니다.

방법들른 노드어떻게 구했나
다 놓아 본 뒤 검사(완전 탐색)
놓을 때마다 검사(가지치기)

다 놓아 본 뒤 검사하는 쪽의 노드 수는 식으로도 구할 수 있습니다. n 이 8 이상이면 이 쪽은 세지 않고 식의 값을 적습니다(n = 7 까지는 코드로 센 값이 식과 같습니다).

1 + n + n² + … + nⁿ  =  (nⁿ⁺¹ − 1) ÷ (n − 1)

해 볼 것. ① 처음 값 n = 8 은 19,173,961(식) 대 2,057 로, 가지치기 쪽이 약 9,321분의 1 만 들릅니다. 답은 92개입니다. ② n = 4 는 341 대 17, 답 2개입니다. 이 17 은 1절의 트리에서 빈 판 1, 1줄 4, 2줄 6, 3줄 4, 4줄 2 를 더한 것입니다. ③ n = 10 은 11,111,111,111(식) 대 35,539, 답 724개입니다. ④ 가지치기 쪽도 n 이 7, 8, 9, 10 으로 하나씩 늘 때 552 → 2,057 → 8,394 → 35,539 로 매번 4 배 안팎씩 늡니다. 막힌 가지를 일찍 버려도 트리 자체가 지수로 크기 때문입니다.

5. 꼭 알아야 할 성질

성질쉬운 말실험에서
답을 빠뜨리지 않는다버리는 것은 이미 틀린 가지뿐이라, 끝까지 돌면 모든 답을 찾는다n = 8 의 답 92개. 두 방법의 답 수가 같다
빠르기는 가지치기가 정한다일찍 검사할수록 위에서 큰 가지를 버린다n = 8: 19,173,961 → 2,057
가장 나쁠 때는 여전히 지수n 이 하나 늘면 몇 배씩 는다. 큰 판에서는 가지치기만으로 모자라다552 → 2,057 → 8,394 → 35,539
메모리는 지금 길 하나트리를 저장하지 않는다. 지금 고른 것들의 목록(깊이만큼)만 든다퀸 n 개의 칸 목록 하나
첫 답까지의 걸음은 들쭉날쭉하다첫 가지에서 바로 답이 나오기도 하고, 한참 되돌아가기도 한다n = 5 는 15걸음, n = 6 은 217걸음, n = 7 은 46걸음

6. 언제 무엇을 쓰나: 그리디, 동적 계획법과 비교

방법하는 일좋은 점나쁜 점걸리는 시간(좋을 때 · 보통 · 나쁠 때)더 드는 메모리쓰는 경우
백트래킹고를 것을 하나씩 정하며 깊이 우선으로 돌고, 틀린 가지는 버리고 되돌아간다답을 빠뜨리지 않는다. 짜기 쉽다가장 나쁠 때 지수로 는다좋을 때: 첫 가지에서 바로 답(깊이만큼). 보통: 문제와 가지치기에 따라 크게 다르다. 나쁠 때: 갈래가 b, 깊이가 d 면 bᵈ 쯤(n 이 하나 늘면 몇 배, O(bᵈ))지금 길 하나(깊이만큼, O(d))조건을 만족하는 배치 찾기, 모든 조합·순열 만들기
그리디지금 가장 좋아 보이는 것 하나를 고르고 되돌아가지 않는다빠르고 단순하다그 고름이 끝까지 맞다고 보일 수 있는 문제에서만 맞는 답이 나온다고를 것을 한 번씩 보면 끝. 먼저 정렬하면 O(n log n)(n 이 두 배면 두 배 조금 넘게). 좋을 때·나쁠 때가 거의 같다적다(정렬에 드는 만큼)지금 고름이 나중을 망치지 않는 문제
동적 계획법같은 작은 문제의 답을 표에 적어 두고 다시 쓴다되풀이되는 계산을 한 번만 한다작은 문제로 나누는 법(상태)을 찾아야 하고, 표를 둘 메모리가 든다상태 수 × 상태 하나의 계산. 표를 다 채우면 좋을 때·나쁠 때가 같다상태 수만큼같은 작은 문제가 되풀이되는 최솟값·최댓값·개수 문제

빅오 표기는 시간 복잡도 쪽에서 다룹니다.

어디에 쓰나

자주 묻는 것

백트래킹과 깊이 우선 탐색은 같은 것인가요?

백트래킹은 고를 것의 트리를 깊이 우선으로 도는 방법입니다. 깊이 우선 탐색은 도는 순서이고, 백트래킹은 그 순서에 「놓을 때마다 검사해 틀린 가지를 버리기」와 「올라올 때 고른 것을 되돌리기」를 더한 것입니다.

꼭 재귀로 짜야 하나요?

아닙니다. 이 쪽의 실험 ① 은 반복문과 목록 하나(지금 놓인 퀸들)로 짰습니다. 재귀로 짜면 「어디로 되돌아갈지」를 함수 호출이 기억해 주어 코드가 짧을 뿐, 하는 일은 같습니다.

언제 백트래킹 대신 다른 방법을 찾아야 하나요?

같은 작은 문제가 여러 번 되풀이되면 그 답을 저장해 다시 쓰는 동적 계획법을, 지금 가장 좋아 보이는 것을 고르면 끝까지 맞는다고 보일 수 있으면 그리디를 먼저 봅니다. 백트래킹은 조건을 만족하는 배치를 찾거나 모든 경우를 하나씩 만들어야 할 때 씁니다.

낱말

여기서 쓴 말책에서 부르는 말
가 보고 막히면 되돌아오기백트래킹, 되추적(backtracking)
고를 것을 하나씩 정해 가는 트리상태 공간 트리(state space tree), 탐색 트리(search tree)
퀸을 놓은 상태 하나, 빈 판, 다 놓은 배치노드(node), 루트(root), 리프(leaf)
이미 틀린 가지를 버리기가지치기(pruning)
한 가지를 끝까지 내려가 보기깊이 우선 탐색(depth-first search, DFS)
다 놓아 본 뒤 검사완전 탐색, 무차별 대입(brute force), 생성 후 검사(generate and test)
퀸 놓기N-퀸 문제(N-Queens problem)
조건을 만족하는 배치 찾기제약 충족 문제(constraint satisfaction problem)
순서를 바꿔 늘어놓기, 몇 개 고르기순열(permutation), 조합(combination)
n 이 하나 늘면 몇 배지수 시간(exponential time)

출처

← 동적 계획법