백트래킹의 개념

백트래킹(backtracking)은 답을 한 번에 만들지 않고 한 칸씩 채워 가다가, 지금까지 고른 것이 조건을 어기면 바로 앞 단계로 돌아가 다른 선택을 시도하는 탐색 기법입니다. 모든 경우를 끝까지 만들어 본 뒤 검사하는 완전 탐색과 달리, 가망이 없는 길은 중간에 잘라 내므로 같은 문제를 훨씬 적은 시도로 풀 수 있습니다. 이 장에서는 백트래킹을 설명할 때 쓰는 용어와 기본 틀, 그리고 언제 백트래킹을 고르는지 정리합니다.

상태 공간 트리

백트래킹이 탐색하는 공간은 상태 공간 트리(state-space tree)로 그리면 이해하기 쉽습니다. 루트는 아무것도 고르지 않은 빈 상태이고, 한 단계 내려갈 때마다 선택을 하나씩 더합니다. 리프에 도착하면 완성된 후보 하나가 만들어집니다. 예를 들어 [1, 2, 3]의 순열을 만드는 트리는 다음과 같습니다.

                 []
       /         |         \
     [1]        [2]        [3]
    /   \      /   \      /   \
 [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
   |     |     |     |     |     |
[1,2,3] ...                    [3,2,1]

백트래킹은 이 트리를 깊이 우선 탐색(DFS)으로 내려가되, 어떤 노드가 더 내려가 봐야 해가 될 수 없다고 판단되면 그 아래 가지 전체를 건너뜁니다. 이것을 가지치기(pruning)라고 합니다.

꼭 알아야 할 용어

• 부분해(partial solution): 지금까지 고른 선택들의 목록입니다. 보통 path 같은 리스트로 들고 다닙니다.
• 후보(candidate): 현재 상태에서 다음에 고를 수 있는 값들입니다.
• 유망성(promising): 현재 부분해를 더 늘려서 해에 도달할 가능성이 남아 있는지 여부입니다.
• 가지치기: 유망하지 않은 노드에서 탐색을 멈추고 돌아가는 일입니다.
• 제약 조건(constraint): 해가 반드시 지켜야 하는 규칙입니다. 같은 열에 퀸을 두 개 놓지 않는다, 합이 목표를 넘지 않는다 같은 것들입니다.

선택 · 탐색 · 되돌리기

거의 모든 백트래킹 코드는 세 동작의 반복입니다. 후보를 하나 선택(choose)해 부분해에 넣고, 그 상태에서 재귀로 탐색(explore)한 뒤, 돌아와서 넣었던 것을 되돌립니다(unchoose). 되돌리기가 있어야 하나의 path 리스트를 모든 가지가 함께 쓸 수 있습니다.

def backtrack(path, choices, result):
    if is_solution(path):
        result.append(path[:])      # 복사해서 저장
        return
    for c in candidates(path, choices):
        if not is_valid(path, c):   # 가지치기
            continue
        path.append(c)              # 선택
        backtrack(path, choices, result)  # 탐색
        path.pop()                  # 되돌리기

result.append(path[:])에서 복사를 빼먹으면, 나중에 path가 비워질 때 저장해 둔 결과도 같이 바뀌어 빈 리스트만 남습니다. 백트래킹에서 가장 흔한 실수 가운데 하나입니다.

작은 예: 부분집합

각 원소를 넣을지 말지 두 갈래로 나누면 부분집합 트리가 됩니다. 원소가 n개면 리프가 2^n개입니다.

def subsets(nums):
    result, path = [], []

    def dfs(i):
        if i == len(nums):
            result.append(path[:])
            return
        path.append(nums[i])   # nums[i]를 넣는 가지
        dfs(i + 1)
        path.pop()
        dfs(i + 1)             # 넣지 않는 가지

    dfs(0)
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

가지치기가 있는 예

길이 n의 0/1 문자열 가운데 1이 연속으로 붙지 않는 것만 만들어 봅니다. 마지막 글자가 1이면 다음에 1을 고르지 않는 것이 가지치기입니다. 잘못된 문자열을 다 만든 뒤 걸러 내는 것보다 훨씬 적게 탐색합니다.

def no_adjacent_ones(n):
    out = []

    def dfs(s):
        if len(s) == n:
            out.append(s)
            return
        dfs(s + "0")
        if not s.endswith("1"):   # 1 다음 1은 시도하지 않음
            dfs(s + "1")

    dfs("")
    return out

print(no_adjacent_ones(3))  # ['000', '001', '010', '100', '101']

언제 백트래킹을 쓰나

• 조건을 만족하는 해를 모두 나열해야 할 때: 순열, 조합, 부분집합, 경로 목록.
• 제약 충족 문제(CSP)를 풀 때: N-Queens, 스도쿠, 색칠 문제, 일정 배치.
• 입력이 작아서(대략 n이 20 안팎 이하) 지수 시간이라도 감당할 수 있을 때.
• 하위 문제가 겹치지 않아 동적 계획법(DP)으로 결과를 재사용하기 어려울 때.

반대로 개수만 세면 되고 같은 하위 문제가 반복된다면 DP가, 매 단계의 최선 선택이 전체 최적을 보장한다면 그리디가 더 알맞습니다. 이 비교는 복잡도 장에서 자세히 다룹니다.

정리

• 백트래킹은 상태 공간 트리를 깊이 우선으로 탐색하면서 유망하지 않은 가지를 잘라 내는 기법입니다.
• 코드는 선택 → 탐색 → 되돌리기의 반복이고, 해를 저장할 때는 부분해를 복사합니다.
• 가지치기 조건을 얼마나 일찍, 얼마나 강하게 거느냐가 성능을 좌우합니다.