백트래킹: 막다른 길에서 되돌아가기

프롤로그 - 알고리즘 문제에서 N-Queen을 만났던 날

나는 비전공자 출신이라 알고리즘 문제를 만나면 항상 주눅부터 들었다. 특히 재귀(Recursion)가 나오는 순간 "아, 나는 안 되나 봐"라는 생각이 자동으로 떠올랐다. 그러던 어느 날, 알고리즘 공부를 하다가 N-Queen 문제를 만났다. "8x8 체스판에 퀸 8개를 서로 공격하지 못하게 놓아라." 문제를 읽고 나서 든 생각은 단 하나였다. "이거 그냥 모든 경우의 수를 다 해보면 되는 거 아냐?"

그래서 일단 코드를 짰다. 64칸 중 8개를 고르는 조합을 만들어서 하나하나 체크하는 Brute Force 방식이었다. 돌려봤다. 프로그램이 멈췄다. 3분이 지나도 답이 안 나왔다. 계산기를 두드려봤더니 경우의 수가 44억이 넘었다. "아... 이렇게 풀면 안 되는 거구나." 그때 처음 깨달았다. "똑똑하게 포기하는 법"을 알아야 한다는 걸.

그게 바로 백트래킹(Backtracking)이었다.

고민 - DFS랑 뭐가 다른 거야?

처음 백트래킹을 배울 때 가장 혼란스러웠던 건, "이거 그냥 DFS(깊이 우선 탐색) 아니야?"라는 의문이었다. 재귀 호출로 깊게 들어가는 것도 같고, 스택 구조도 같고, 뭔가 비슷해 보였다. 그런데 찾아보니 미묘한 차이가 있었다. DFS는 "갈 수 있는 곳은 다 간다"는 마인드지만, 백트래킹은 "이 길은 가망이 없으니까 아예 안 간다"는 마인드였다. 이 차이가 엄청난 성능 차이를 만들어냈다.

백트래킹은 단순히 "뒤로 돌아가기"가 아니라 "가지치기(Pruning)"를 포함한 탐색 방식이었다. 나무를 키우듯 가능성 있는 가지만 뻗어나가고, 죽은 가지는 과감하게 잘라내는 것. 이 개념이 와닿고 나서부터 많은 문제가 풀리기 시작했다.

깨달음 - 결국 이거였다 - "빨리 포기하는 기술"

백트래킹을 이해했다고 생각했던 순간, 정규표현식(Regex)을 공부하다가 ReDOS 공격이라는 걸 알게 됐다. (a+)+b 같은 패턴에 aaaaaaa... 문자열을 넣으면 서버 CPU가 100%를 찍고 죽는다는 내용이었다. "정규식 엔진도 백트래킹을 쓰는구나!" 그 순간 깨달았다. 백트래킹은 단순히 알고리즘 문제풀이 기법이 아니라, 우리가 매일 쓰는 수많은 시스템의 핵심 메커니즘이었다.

Cloudflare가 전 세계에 502 에러를 뿌렸던 사건도 이 백트래킹 기반 정규식 엔진의 폭주 때문이었다는 걸 알고는 충격을 받았다. "아, 이 알고리즘은 진짜 쓰이는 거구나." 그래서 나는 백트래킹을 "빨리 포기하는 기술"이라고 정리해봤다. 완벽하게 다 해보려고 하면 시간이 폭발한다. 하지만 "이 길은 안 될 것 같아"라는 직감이 정확하다면, 그 길을 아예 안 가는 것만으로도 엄청난 효율을 얻는다.

핵심 원리 - 상태 공간 트리(State Space Tree)

모든 선택은 거대한 트리(Tree)로 표현할 수 있다. 루트 노드는 아무 선택도 하지 않은 초기 상태이고, 가지(Branch)는 우리가 할 수 있는 선택들이며, 단말 노드(Leaf)는 최종 결과다. 백트래킹은 이 트리를 깊이 우선 탐색(DFS) 방식으로 순회하되, 멍청하게 모든 노드를 방문하지 않는다.

특정 노드에 도착했을 때 "이 길이 가망이 있는가?(Promising)"를 판단한다. Yes라면 자식 노드로 계속 내려가고, No라면 즉시 부모 노드로 되돌아간다. 이게 바로 가지치기(Pruning)다. 이 판단 함수(isPromising())를 얼마나 똑똑하게 짜느냐가 알고리즘의 성능을 결정한다.

비유하자면 이렇다. 미로를 탐험하는데, 특정 통로에 들어서자마자 "어? 여기 막혀 있네"라는 표지판이 보인다면, 끝까지 가보지 않고 바로 돌아오는 것이다. 이 "표지판 읽는 능력"이 백트래킹의 핵심이다.

역사 이야기 - 가우스도 실수했던 8-Queen 문제

N-Queen 문제는 1848년 체스 작곡가 막스 베첼(Max Bezzel)이 처음 제안했다. 하지만 이 문제가 유명해진 건 카를 프리드리히 가우스(Carl Friedrich Gauss)가 1850년에 이 문제에 꽂혔기 때문이다. 수학의 황태자라 불리던 가우스는 펜과 종이만으로 이 문제를 풀려고 시도했다. 그때는 컴퓨터가 없었으니 가우스의 두뇌가 곧 CPU였다.

그는 72개의 해답을 찾아냈다. 하지만 실제 정답은 92개였다. 천하의 가우스조차 사람인지라 실수를 피할 수 없었던 것이다. 만약 가우스에게 백트래킹 알고리즘과 컴퓨터가 있었다면, 0.001초 만에 92개를 다 찾았을 것이다. 이 일화는 알고리즘적 사고(Algorithmic Thinking)가 천재의 직관보다 더 강력할 수 있음을 보여준다.

나는 이 이야기를 알고 나서 위안을 받았다. "가우스도 못 찾은 걸 내가 못 찾는 게 당연하지." 하지만 동시에 깨달았다. "그래도 나는 컴퓨터가 있잖아." 알고리즘을 제대로 이해하고 구현할 수 있다면, 우리는 가우스를 뛰어넘을 수 있다.

구체적인 예제 1 - N-Queen 문제 구현

N-Queen 문제를 다시 보자. 8x8 체스판에서 무식하게 모든 경우를 따지면 $64C8 \approx 44$억 가지다. 컴퓨터로도 몇 분이 걸린다. 하지만 백트래킹을 쓰면 수천 가지로 줄어든다.

def solve_n_queens(n):
    board = [-1] * n  # board[row] = col
    results = []

    def is_safe(row, col):
        for prev_row in range(row):
            prev_col = board[prev_row]
            # 세로 열 겹침 or 대각선 겹침
            if prev_col == col or abs(prev_col - col) == abs(prev_row - row):
                return False
        return True

    def backtrack(row):
        if row == n:
            results.append(list(board))  # 해답 발견!
            return

        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                backtrack(row + 1)  # 재귀 호출
                board[row] = -1  # 되돌리기 (Backtrack)

    backtrack(0)
    return results

여기서 핵심은 is_safe() 함수다. 이 함수가 "가망성 판단"을 한다. 만약 어떤 칸에 퀸을 놓았을 때 이미 놓인 퀸과 충돌한다면, 그 칸은 아예 시도하지 않는다. 이게 가지치기다.

그리고 또 하나 중요한 건 board[row] = -1 이 부분이다. 재귀 호출에서 빠져나왔을 때 상태를 원상복구(Clean up)해야 다음 탐색에 영향을 주지 않는다. 이 부분을 빼먹는 게 주니어 개발자들이 가장 많이 하는 실수다. 나도 처음에 이거 빼먹고 3시간 디버깅했던 기억이 있다.

구체적인 예제 2 - 스도쿠(Sudoku) 풀이

스도쿠도 백트래킹의 전형적인 예제다. 사람이 푸는 방식 그대로다. 다만 컴퓨터는 초당 수백만 번 썼다 지웠다를 반복할 뿐이다.

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True  # 빈칸이 없으면 완성!
    row, col = empty

    for num in range(1, 10):
        if is_valid(board, num, (row, col)):
            board[row][col] = num  # 시도

            if solve_sudoku(board):  # 재귀
                return True

            board[row][col] = 0  # 실패! 되돌리기

    return False  # 1~9 다 안 됨 -> 이전 단계로 Back

def is_valid(board, num, pos):
    # 가로, 세로, 3x3 박스 체크
    # ... (생략)
    return True

board[row][col] = 0 이 한 줄이 바로 백트래킹이다. 이 줄이 없으면 알고리즘은 막다른 길에서 영원히 멈춰버린다.

비트마스크(Bitmask) 최적화로 10배 빠르게 깊이 들여다보기

N-Queen 문제를 풀다가 "시간 초과"가 떴던 경험이 있다. 배열 방식으로는 한계가 있었다. 그때 알게 된 게 비트마스크(Bitmask) 최적화였다. 처음에는 "비트 연산? 너무 어려운데"라고 생각했지만, 막상 써보니 엄청나게 빨랐다. 배열 방식보다 10배 이상 빠른 속도를 경험했다.

def solve(row, cols, d1, d2):
    if row == N:
        return 1

    count = 0
    # 놓을 수 있는 자리들을 비트 연산으로 한 번에 계산
    available = ~(cols | d1 | d2) & ((1 << N) - 1)

    while available:
        # 가장 오른쪽의 1인 비트(위치)를 가져옴
        curr = available & -available
        available -= curr

        # 재귀 호출 (비트 시프트로 대각선 처리)
        count += solve(row + 1, cols | curr, (d1 | curr) << 1, (d2 | curr) >> 1)

    return count

이 방식은 메모리 접근을 최소화하고 CPU의 비트 연산기(ALU)를 극한으로 활용한다. 처음에는 이해가 안 갔지만, "cols는 세로 열 점유 상태", "d1은 왼쪽 대각선 점유 상태", "d2는 오른쪽 대각선 점유 상태"라고 정리해본 후 코드가 눈에 들어왔다. 이런 최적화를 경험하고 나서 비트 연산의 매력에 빠졌다.

실제 응용 - 정규표현식과 ReDOS 공격

우리는 매일 백트래킹을 쓰고 있다. 바로 정규표현식(Regex) 엔진이다. a*b 패턴을 찾을 때, 엔진은 a를 최대한 많이 매칭해보고(Greedy), 뒤에 b가 없으면 하나씩 a를 뱉어내며(Backtrack) 다시 시도한다.

그런데 여기서 문제가 생긴다. 만약 패턴을 (a+)+b처럼 짜면 어떻게 될까? 백트래킹의 경우의 수가 지수적으로 폭발(Exponential Blowup)한다. 공격자가 aaaaaaaaa... 같은 문자열을 보내면, 서버 CPU는 이걸 매칭하느라 100%를 찍고 멈춰버린다. 이것이 ReDOS(Regular Expression Denial of Service) 공격이다.

실제로 Cloudflare가 전 세계에 502 Bad Gateway를 띄웠던 원인도 이 백트래킹 기반 정규식 엔진의 폭주 때문이었다. 이 사건을 알고 나서 나는 정규식을 쓸 때 항상 조심하게 됐다. "이 패턴이 백트래킹을 많이 유발하지는 않을까?" 그래서 Go나 Rust의 정규식 엔진은 백트래킹 대신 Thompson's Construction (NFA) 방식을 써서 $O(N)$을 보장한다. 이런 차이를 알고 나니 언어 선택도 달라졌다.

한계 - P vs NP 문제

백트래킹은 훌륭하지만 만능은 아니다. 최악의 경우, 가지치기가 거의 안 된다면? 결국 모든 경우의 수를 다 뒤져야 하므로 $O(2^N)$ 또는 $O(N!)$이라는 절망적인 시간이 걸린다. 이런 문제들을 NP-Complete 문제라고 한다. 외판원 순회 문제(TSP) 같은 거다. N이 100만 넘어가면 우주가 멸망할 때까지 답이 안 나온다.

이럴 때는 백트래킹을 포기하고, "적당히 괜찮은 답"을 찾는 유전 알고리즘(Genetic Algorithm)이나 메타휴리스틱을 써야 한다. 완벽함(Optimum)을 포기하면 속도(Speed)를 얻을 수 있으니까. 나는 이 트레이드오프를 받아들이고 나서 "모든 문제를 완벽하게 풀 필요는 없구나"라고 생각하게 됐다.

백트래킹 vs 동적계획법(DP)

처음 배울 때 이 둘을 엄청 헷갈려했다. "둘 다 재귀 쓰는데 뭐가 달라?" 하지만 정리해본 결과, 목적이 완전히 달랐다.

특징	백트래킹	동적계획법 (DP)
목적	모든 가능한 해 탐색	최적해 또는 개수 구하기
방식	가보고 아니면 돌아오기	작은 문제 답 저장해서 재사용
메모리	스택만 씀. 적음	테이블 만듦. 많이 씀
예시	N-Queen, 미로 찾기	피보나치, 배낭 문제(Knapsack)

백트래킹은 "길 찾기", DP는 "최적화"라고 정리해봤다. 0/1 배낭 문제는 둘 다 가능한데, 보통 성능 때문에 DP로 푼다. 하지만 무게(W)가 엄청 크고 N이 작다면 백트래킹이 더 빠를 수도 있다. 이게 알고리즘의 묘미다.

요약

1. 백트래킹 = DFS + 가지치기(Pruning). 가지치기가 생명이다.
2. 빨리 포기하는 놈이 승리한다. 가망 없는 길은 아예 안 가는 게 정답이다.
3. 상태 복구(Undo)를 잊지 말자. board[row] = -1 같은 한 줄이 알고리즘을 살린다.
4. 정규표현식도 백트래킹을 쓴다. ReDOS 공격을 조심하자.
5. 완벽한 답이 안 나오면, 근사해(Approximation)를 찾자. 완벽주의를 포기하면 속도를 얻는다.