[알고리즘 코어 파헤치기] 백트래킹(Backtracking) 완벽 해부 - 가지치기와 상태 복구의 미학

학습 철학 회고
실전에서 itertools를 쓰면 한 줄에 끝날 문제라도, 그 이면에 숨겨진 '상태 공간 트리(State Space Tree)'의 작동 방식을 뼛속까지 이해해야 복잡한 제약 조건이 걸린 시뮬레이션 문제를 통제할 수 있습니다.

📌 개념 요약: 백트래킹은 무엇인가?

모든 가능한 경우의 수를 전부 탐색하는 브루트 포스(Brute Force)를 기반으로 하되, "이 길이 아니면 즉시 뒤로 돌아간다"는 철학을 더한 영리한 완전 탐색입니다.

• 상태 공간 트리 (State Space Tree): 내가 선택할 수 있는 모든 경우의 수를 나무의 가지처럼 펼쳐놓은 가상의 공간입니다.
• 가지치기 (Pruning): 재귀로 트리를 타고 내려가다가, 문제의 조건에 위배되는 순간 더 이상 깊이 들어가지 않고 부모 노드로 돌아(Back)가는 최적화 기법입니다.

💡 동작 원리: 상태의 전이와 복구

백트래킹의 심장은 바로 '상태 복구'에 있습니다. 재귀 함수가 하나의 세계선(Branch)을 탐색하고 부모 노드로 돌아왔을 때, 이전의 행동을 완벽하게 '없던 일'로 만들어주어야 다음 평행 세계(다른 Branch)를 온전하게 탐색할 수 있습니다.

💻 추상화된 템플릿 코드

어떤 순열/조합이나 N-Queen 문제에도 적용할 수 있는 가장 순수한 백트래킹 구조입니다.

def backtracking_template(depth, target_depth, path):
    """
    :param depth: 현재까지 탐색한 깊이 (선택한 개수)
    :param target_depth: 도달해야 하는 목표 깊이 (M개)
    :param path: 현재까지 선택한 경로를 담은 리스트
    """
    
    # 1. 종료 조건 (Base Condition)
    if depth == target_depth:
        print(path) # 정답 처리 또는 출력
        return
        
    # 2. 다음 상태 탐색 (상태 공간 트리의 자식 노드들)
    for i in range(1, 5): # 예시: 1부터 4까지의 후보
        
        # [가지치기 로직 삽입부]
        # if i in path: continue (순열의 경우 중복 방지)
        
        # 3. 상태 변화 (선택)
        path.append(i)
        
        # 4. 다음 뎁스로 깊이 파고들기
        backtracking_template(depth + 1, target_depth, path)
        
        # 5. [핵심] 상태 복구 (원상 복구하여 다음 평행 세계 탐색 준비)
        path.pop() 

# 실행
backtracking_template(0, 3, [])

🚨 설계 및 회고

• append와 pop의 대칭성: 선택을 했으면(append), 재귀가 끝난 직후 반드시 그 선택을 취소(pop)해야 합니다. 이 대칭성이 깨지면 전역 상태가 오염되어 원치 않는 쓰레기 데이터가 누적됩니다.
• 조합(Combination)으로의 변형: 순열이 아니라 조합을 구하고 싶다면, 반복문이 항상 '이전 선택보다 큰 값'부터 시작하도록 재귀 함수에 start 파라미터를 하나 더 넘겨주는 것만으로 우아하게 가지치기를 구현할 수 있습니다.