CS학습2026년 8월 23일

Backtracking: 유망하지 않은 경로를 즉시 포기하는 완전탐색

백트래킹(Backtracking)은 해를 단계적으로 구성하면서 조건을 만족하지 못하는 순간 이전 상태로 되돌아가 탐색 범위를 줄이는 알고리즘 기법이다. 모든 경우의 수를 나열하는 완전탐색(Brute-force)과 달리 유망성 검사(Pruning)를 통해 불필요한 분기를 조기에 차단한다. N-Queens, 순열/조합 생성, 스도쿠 같은 제약 충족 문제(Con

송민성6분 읽기

1. 개념

백트래킹(Backtracking)은 해를 구성하는 후보를 하나씩 선택해나가다가, 그 선택이 문제의 제약 조건을 위반하는 것으로 판명되면 즉시 선택을 취소하고(백트랙, backtrack) 이전 상태로 돌아가 다른 후보를 시도하는 알고리즘 기법이다.

본질적으로는 깊이 우선 탐색(DFS, Depth-First Search)을 상태 공간 트리(State Space Tree)에 적용한 것이다. 다만 일반 DFS와 다른 점은 각 노드에 진입할 때마다 "이 경로가 답이 될 가능성이 있는가"를 검사하는 유망성 검사(Promising Check / Pruning)를 수행한다는 것이다. 가능성이 없다고 판단되면 그 노드의 하위 트리 전체를 탐색하지 않고 건너뛴다.

2. 왜 사용하는가

순열, 조합, 부분집합 같은 문제는 후보 개수가 팩토리얼(n!) 또는 지수(2^n) 단위로 폭발적으로 증가한다. 이걸 전부 생성한 뒤 조건을 검사하면 시간 낭비가 심하다.

백트래킹은 해를 "부분적으로" 만들어가는 도중에 이미 조건을 위반했다는 걸 알 수 있다면 그 순간 가지치기(Pruning)를 해서 이후의 모든 하위 경우를 한꺼번에 배제한다. 예를 들어 N-Queens 문제에서 첫 번째 퀸과 두 번째 퀸이 이미 서로 공격 가능한 위치라면, 세 번째 퀸부터 여덟 번째 퀸까지의 모든 배치 조합을 검사할 필요가 없어진다.

3. 동작 원리

백트래킹은 다음 구조를 따른다.

선택(Choose): 현재 상태에서 가능한 후보 중 하나를 선택해 부분해에 추가한다.
제약 검사(Constraint Check): 선택한 후보가 문제의 제약 조건을 만족하는지 확인한다.

- 만족하지 않으면 즉시 3번(되돌리기)으로 간다.

재귀 탐색(Explore): 조건을 만족하면 다음 단계로 재귀 호출을 한다. 만약 부분해가 완성된 해라면 결과에 기록한다.
되돌리기(Unchoose / Backtrack): 재귀 호출이 끝나면 방금 추가한 선택을 제거하고 다음 후보를 시도한다.

이 과정을 의사코드로 표현하면 다음과 같다.

text

def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for candidate in generate_candidates(state):
        if is_valid(state, candidate):
            state.add(candidate)       # 선택
            backtrack(state)           # 탐색
            state.remove(candidate)    # 되돌리기

핵심은 state.remove(candidate) 부분이다. 재귀 호출에서 돌아온 뒤 상태를 원래대로 복구해야 형제 노드(sibling node)를 올바르게 탐색할 수 있다.

4. 코드 예제

예제 1: N-Queens (제약 충족 문제의 대표 예시)

python

def solve_n_queens(n: int) -> list[list[int]]:
    solutions = []
    cols = set()          # 사용 중인 열
    diag1 = set()         # row - col 이 같으면 같은 대각선
    diag2 = set()         # row + col 이 같으면 같은 대각선
    board = [-1] * n      # board[row] = col

    def backtrack(row: int):
        if row == n:
            solutions.append(board.copy())
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # 유망하지 않음 -> 가지치기

            # 선택
            board[row] = col
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)  # 재귀 탐색

            # 되돌리기
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

        board[row] = -1

    backtrack(0)
    return solutions


if __name__ == "__main__":
    results = solve_n_queens(4)
    print(f"4-Queens 해의 개수: {len(results)}")
    for r in results:
        print(r)

실행 결과:

text

4-Queens 해의 개수: 2
[1, 3, 0, 2]
[2, 0, 3, 1]

예제 2: 부분집합 합 (Subset Sum) — 가지치기 유무 비교

python

def subset_sum(nums: list[int], target: int) -> list[list[int]]:
    nums.sort()  # 가지치기를 위해 정렬 필수
    results = []
    path = []

    def backtrack(start: int, remaining: int):
        if remaining == 0:
            results.append(path.copy())
            return
        if remaining < 0:
            return

        for i in range(start, len(nums)):
            # 가지치기: 정렬된 상태에서 남은 값보다 큰 수가 나오면 이후는 모두 실패
            if nums[i] > remaining:
                break

            path.append(nums[i])
            backtrack(i + 1, remaining - nums[i])  # 재귀 탐색
            path.pop()  # 되돌리기

    backtrack(0, target)
    return results


print(subset_sum([2, 3, 5, 6, 7], 10))
# [[2, 3, 5], [3, 7]]

5. 시간 복잡도 또는 성능 특성

백트래킹의 시간 복잡도는 문제마다 다르며, 최악의 경우 가지치기가 전혀 작동하지 않으면 완전탐색과 동일한 복잡도를 갖는다.

N-Queens: 최악의 경우 O(n!)에 가깝지만, 열·대각선 충돌 검사로 실제 탐색되는 노드 수는 훨씬 적다. n=8일 때 완전탐색은 8^8 ≈ 1,677만 가지를 시도해야 하지만, 백트래킹은 대략 수만 번의 시도로 92개의 해를 모두 찾는다.
순열 생성: O(n!) — 가지치기 여지가 없는 경우 완전탐색과 동일하다.
부분집합/조합 생성: O(2^n) — 상태 공간 트리의 크기 자체가 지수적이다.

가지치기의 효과는 "얼마나 일찍, 얼마나 자주 유망성 검사에 실패하는가"에 달려 있다. 가지치기 조건이 강할수록 실제 탐색 노드 수는 이론적 상한보다 크게 줄어들지만, 빅오(Big-O) 표기 자체는 최악의 경우를 기준으로 하므로 여전히 지수 시간대에 속한다는 점은 변하지 않는다.

6. 실무 사용 사례

제약 충족 문제(CSP) 해결: 스도쿠 솔버, 크로스워드 퍼즐, 그래프 색칠(Graph Coloring) 문제.
조합 최적화 초기 단계: 브랜치 앤 바운드(Branch and Bound) 기법의 기반이 되며, 정수계획법(Integer Programming) 솔버 내부에서도 유사한 원리가 쓰인다.
자연어 처리 및 컴파일러: 정규식 엔진의 백트래킹 매칭(예: Perl 호환 정규식의 그리디 매칭 실패 시 되돌아가기), 파서의 구문 분석 실패 시 복구.
게임 AI: 스도쿠, 8-퍼즐, 미로 탐색에서 가능한 경로를 탐색하되 막다른 길이면 되돌아가는 로직.
권한/설정 조합 테스트: 여러 옵션의 조합 중 특정 제약을 만족하는 조합만 찾아야 하는 설정 검증 로직.

7. 주의할 점

상태 복구 누락: 재귀 호출 이후 remove/pop 같은 되돌리기 연산을 빠뜨리면 형제 노드 탐색 시 이전 선택의 흔적이 남아 잘못된 결과가 나온다. 가변 객체(list, set)를 상태로 쓸 때 특히 주의해야 한다.
가지치기 조건의 정확성: 유망성 검사가 너무 느슨하면 성능 개선 효과가 없고, 너무 엄격하면 정답을 놓칠 수 있다. 정렬이 필요한 경우(위 부분집합 합 예제)를 놓치기 쉽다.
얕은 복사 vs 깊은 복사: 해를 결과 리스트에 저장할 때 path.copy() 없이 path 자체를 저장하면, 이후 pop() 연산으로 저장된 결과까지 함께 변경되는 버그가 발생한다.
재귀 깊이 제한: Python은 기본 재귀 깊이 제한이 1000이다. 입력 크기가 크면 sys.setrecursionlimit() 조정이나 반복문 기반 명시적 스택(explicit stack) 구현을 고려해야 한다.
지수 시간 폭발: 가지치기가 잘 작동하지 않는 문제 구조라면 여전히 지수 시간이 걸린다. 문제 크기가 커지면 동적 계획법(DP)이나 근사 알고리즘 같은 대안을 검토해야 한다.

8. 핵심 정리

백트래킹은 "선택 → 검사 → 재귀 → 되돌리기"의 4단계를 반복하는 DFS 기반 완전탐색 기법이며, 유망성 검사를 통한 가지치기로 탐색 공간을 줄이는 것이 핵심이다. 최악의 경우 시간 복잡도는 완전탐색과 동일하지만, 실제로는 가지치기 덕분에 훨씬 적은 노드만 방문한다. 상태를 가변 객체로 관리할 때는 재귀 호출 후 반드시 원상 복구해야 하며, 이 원칙만 지키면 순열·조합·CSP류 문제 대부분에 동일한 템플릿을 적용할 수 있다.