백트래킹 쉽게 이해하기: 동작 원리, 코드, 예제

백트래킹이 해결하는 문제

규칙을 만족하는 모든 배치, 또는 그런 배치 하나를 요구하는 문제가 있습니다. 서로 공격하지 않도록 퀸 8개 놓기, 스도쿠 채우기, 합이 목표값이 되는 집합의 모든 부분집합 나열하기, 문자열을 사전의 단어들로 나누는 모든 방법 찾기가 그 예입니다. 영리한 공식은 없고 탐색해야 합니다. 완성된 조합을 무작정 전부 시도하면 너무 느리지만, 대부분의 부분 조합은 몇 번의 선택만으로도 이미 유효하지 않습니다.

백트래킹은 선택 하나하나가 끝날 때마다 규칙을 확인합니다. 부분 해가 규칙을 어기면 탐색 트리의 그 가지 전체를 즉시 포기하고 돌아가 다음 선택지를 시도합니다.

핵심 아이디어

1. 현재 부분 해가 완성되었다면 기록합니다.
2. 그렇지 않다면 가능한 다음 선택마다, 그 선택이 허용될 경우 선택을 수행합니다(choose).
3. 재귀 호출로 해를 더 확장합니다(explore).
4. 선택을 취소하여 다음 선택지가 같은 상태에서 시작하도록 합니다(unchoose).

탐색 공간은 트리입니다. 루트는 빈 해이고, 각 레벨은 선택을 하나씩 더하며, 리프는 완성된 후보입니다. 백트래킹은 이 트리에 대한 깊이 우선 탐색이고, 가지치기는 해를 포함할 수 없는 서브트리를 잘라 내는 것입니다.

예제: 4-Queens

4 × 4 보드에 퀸 4개를 행마다 하나씩, 어떤 두 퀸도 같은 열이나 대각선에 놓이지 않게 배치합니다. 열은 0부터 3까지 번호를 붙입니다.

탐색을 계속하면 유일한 다른 해인 2, 0, 3, 1을 찾으며, 이는 첫 번째 해의 거울상입니다.

파이썬 구현

사용 중인 열과 대각선의 집합을 유지하면 안전 검사를 O(1)에 할 수 있습니다. 한 대각선에서는 row - col이 일정하고 다른 대각선에서는 row + col이 일정합니다.

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

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

같은 템플릿으로 모든 부분집합과 모든 순열을 생성할 수 있습니다.

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

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

단순한 부분집합과 순열은 실제 코드에서 itertools.combinations와 itertools.permutations가 더 빠릅니다. 문제 고유의 규칙으로 가지치기해야 할 때 직접 백트래킹을 작성하세요.

시간 복잡도와 공간 복잡도

백트래킹은 출력 크기보다 빠를 수 없습니다. n!개의 순열을 나열해야 한다면 최소 n!번의 단계가 필요합니다. 가지치기는 아무것도 만들지 못하는 가지를 건너뛸 때만 도움이 됩니다.

변형과 흔한 실수

• 되돌리기를 잊음: 재귀 호출 뒤에 상태를 복원하지 않으면 이후의 가지가 오래된 선택을 보게 됩니다.
• 살아 있는 리스트를 그대로 추가함: result.append(current)는 나중에 바뀌는 참조를 저장합니다. current.copy()를 추가하세요.
• 입력의 중복: 항목을 정렬하고 같은 깊이에서 이전 항목과 같은 항목을 건너뛰면 중복된 부분집합이나 순열을 피할 수 있습니다.
• 첫 해에서 멈추기: 해 하나면 충분할 때는 스도쿠 풀이기처럼 재귀에서 True를 반환하고 반복문을 멈춥니다.
• 더 나은 순서: 가장 제약이 많은 선택을 먼저 시도합니다(스도쿠라면 후보가 가장 적은 빈 칸). 트리가 극적으로 줄어드는 경우가 많습니다.

언제 쓰는지와 실제 활용

• 제약 충족 문제: 스도쿠, 십자말풀이, 지도 색칠, 시간표 짜기, 시험 일정 짜기.
• SAT 솔버와 Prolog 방식의 논리 엔진은 강력한 가지치기를 갖춘 백트래킹 탐색을 기반으로 만들어집니다.
• 파이썬의 re를 포함해 여러 언어의 정규 표현식 엔진은 백트래킹을 사용하며, 잘못 작성한 패턴은 지수적으로 백트래킹할 수 있습니다("치명적 백트래킹").
• 코딩 인터뷰 문제: 부분집합, 순열, 조합의 합, N-Queens, 격자에서 단어 찾기, 팰린드롬 분할, 괄호 생성, 전화번호 문자 조합.