[5주차] 상태 공간 트리와 백트래킹

팔랑이·2025년 12월 23일

알고리즘 자료구조

자료구조/알고리즘

목록 보기

17/19

오늘의 주제

상태 공간 트리

백트래킹

가지치기 전략

활용 예제

상태 공간 트리(State Space Tree)

상태 공간 트리는 문제 해결 과정에서 나올 수 있는 모든 상태를 트리 구조로 표현한 개념이다.

상태 공간 트리는 실제로 메모리에 만드는 자료구조가 아니라
탐색 과정을 이해하기 위해 사용하는 개념적 모델

노드: “현재까지의 선택 결과”를 의미
루트 노드: 아무것도 선택하지 않은 초기 상태
리프: 종료 상태

트리의 깊이는 보통 문제의 단계 수와 대응되며,
자식 노드는 다음 단계에서 가능한 선택지를 의미한다.
이때 리프 노드는 하나의 완성된 해이거나, 더 이상 진행할 수 없는 실패 상태가 된다.

백트래킹(Backtracking)

백트래킹 알고리즘은 모든 가능한 해를 탐색하는 완전 탐색 기반 알고리즘이다.

초기 상태에서 시작하여 가능한 선택을 하나씩 시도하고, 조건을 만족하는 해를 발견하면 이를 기록한다.

모든 선택을 시도하거나 더 이상 유효한 해가 될 수 없는 경우에는 이전 상태로 되돌아가 (=> 백트래킹!) 다른 선택을 탐색한다.

백트래킹은 일반적으로 DFS(깊이 우선 탐색) 방식으로 상태 공간을 탐색한다.
트리의 전위·중위·후위 순회 역시 DFS의 한 형태이며, 이를 기반으로 백트래킹 과정을 설명할 수 있다.

Attempt / Backtrack

백트래킹의 핵심은 Attempt(시도) 와 Backtrack(되돌리기) 이다.

Attempt

현재 상태에서 하나의 선택을 수행
상태(state)를 갱신하며 탐색을 한 단계 진행

Backtrack

해당 선택으로 더 이상 탐색할 수 없거나 탐색이 끝난 경우,
이전 상태로 정확히 복구한다.

이 두 과정은 항상 쌍으로 동작하며,
코드에서는 보통 상태 추가 → 재귀 호출 → 상태 제거 형태로 나타난다.

가지치기(Pruning)

백트래킹 문제에는 보통 제약 조건(constraint) 이 포함되며, 이 제약 조건을 이용해 Pruning(가지치기) 을 수행할 수 있다.

탐색 중 조건을 위반하는 상태를 만나면 해당 상태 아래의 모든 탐색을 즉시 중단하는데, 이를 통해 불필요한 탐색 경로를 제거하고 시간과 공간 효율을 크게 개선할 수 있다.

결과적으로 백트래킹은 상태 공간 트리 전체를 탐색하는 것이 아니라,
가지치기를 통해 유망한 경로만 선택적으로 탐색하게 된다.

예시 코드 (python)

def backtrack(state, choices, res):
    # 1. 해 검사
    if is_solution(state):
        res.append(state.copy())
        return

    # 2. 선택지 탐색
    for choice in choices:
    
        # 3. 가지치기 (pruning)
        if not is_valid(state, choice):
            continue

        # 4. Attempt
        state.append(choice)
        # 5. 다음 상태 탐색
        backtrack(state, next_choices(choice), res)
        # 6. Backtrack
        state.pop()