상태 공간 트리(State Space Tree)

백트래킹 알고리즘을 제대로 이해하기 위해서는 “상태 공간 트리(State Space Tree)“라는 개념을 먼저 파악하는 것이 매우 중요하다.
이 개념은 백트래킹의 이론적 기초가 되며, 문제 해결 과정을 시각적으로 표현하는 데 도움이 된다.

이 트리는 문제 해결 과정의 모든 가능한 경로를 체계적으로 표현하며, 백트래킹은 이 트리를 효율적으로 탐색하는 방법을 제공한다.

상태 공간 트리를 잘 이해하고 설계하면 복잡한 문제도 체계적으로 접근할 수 있다.
특히 상태 표현 방법, 유효성 검사 함수, 가지치기 전략을 최적화하는 것이 효율적인 백트래킹 알고리즘을 개발하는 핵심이다.

상태 공간 트리란 무엇인가?

상태 공간 트리는 문제 해결 과정에서 가능한 모든 상태(state)와 그 상태들 간의 전이(transition)를 트리 형태로 표현한 자료구조이다.
여기서 ‘상태’란 문제 해결 과정에서의 특정 시점의 모든 변수와 조건의 집합을 의미한다.

쉽게 설명하자면, 상태 공간 트리는 문제를 해결하기 위해 취할 수 있는 모든 가능한 선택과 그에 따른 결과를 나무(트리) 형태로 시각화한 것이다.
이 트리의:

루트 노드(Root node): 초기 상태를 나타낸다.
내부 노드(Internal node): 중간 상태(부분적인 해결책)를 나타낸다.
리프 노드(Leaf node): 최종 상태(완전한 해결책 또는 막다른 길)를 나타낸다.
간선(Edge): 한 상태에서 다른 상태로의 전이(결정, 선택)를 나타낸다.

상태 공간 트리와 백트래킹의 관계

백트래킹 알고리즘은 이 상태 공간 트리를 깊이 우선 탐색(DFS, Depth-First Search)하는 방식으로 작동한다. 하지만 일반적인 DFS와 다른 점은 ‘가지치기(pruning)‘를 한다는 것이다. 즉, 더 이상 유망하지 않은 경로(promising하지 않은 노드)를 만나면 탐색을 중단하고 이전 상태로 돌아가(backtrack) 다른 경로를 탐색한다.

백트래킹은 상태 공간 트리의 모든 노드를 방문하지 않고도 해답을 찾을 수 있게 해주는 효율적인 방법이다. 이는 완전 탐색(brute force)보다 훨씬 적은 수의 노드만 방문하면서도 정확한 해답을 찾을 수 있게 해준다.

상태 공간 트리의 구성 요소

상태(State)
상태는 문제 해결 과정의 특정 시점에서의 모든 정보를 담고 있다.
예를 들어, N-Queens 문제에서는 체스판에 배치된 퀸들의 위치가 상태가 된다.
스도쿠 문제에서는 그리드에 채워진 숫자들의 배치가 상태가 된다.
상태는 보통 다음과 같은 정보를 포함한다:
- 현재까지의 선택/결정
- 남은 선택지/가능성
- 현재까지 충족된 제약 조건들
상태 전이(State Transition)
한 상태에서 다른 상태로 이동하는 과정을 상태 전이라고 한다.
이는 결정을 내리거나 선택을 하는 것으로 볼 수 있다.
예를 들어, N-Queens 문제에서는 새로운 퀸을 특정 위치에 배치하는 것이 상태 전이가 된다.
상태 전이는 상태 공간 트리에서 간선(edge)으로 표현된다.
유망한 노드(Promising Node)
백트래킹에서 매우 중요한 개념인 ‘유망한 노드’는 현재 상태에서 계속 탐색을 진행했을 때 해답을 찾을 가능성이 있는 노드를 말한다. 반대로, ‘유망하지 않은 노드’는 아무리 탐색을 계속해도 해답을 찾을 수 없는 노드이다.
백트래킹의 핵심은 유망하지 않은 노드를 조기에 발견하여 불필요한 탐색을 줄이는 것이다. 이를 ‘가지치기(pruning)‘라고 한다.
해답 노드(Solution Node)
해답 노드는 문제의 모든 제약 조건을 만족하는 완전한 해결책을 나타내는 노드이다.
이는 보통 리프 노드(leaf node)이지만, 반드시 그럴 필요는 없다. 문제에 따라 중간 노드도 해답이 될 수 있다.

상태 공간 트리 구현 방법

상태 공간 트리를 구현할 때 고려해야 할 몇 가지 중요한 요소들이 있다:

상태 표현(State Representation)
문제의 상태를 어떻게 프로그래밍적으로 표현할 것인가는 매우 중요하다.
예를 들어:
- N-Queens 문제: 각 행별로 퀸의 열 위치를 저장하는 1차원 배열 (board[i]는 i번째 행에 있는 퀸의 열 위치)
- 부분집합 합 문제: 선택한 요소들의 집합 또는 선택 여부를 나타내는 불리언 배열
- 스도쿠: 9x9 그리드를 나타내는 2차원 배열
  상태 표현은 간결하면서도 모든 필요한 정보를 담을 수 있어야 한다.

유효성 검사 함수(Validity Check Function)
현재 상태가 문제의 제약 조건을 만족하는지 확인하는 함수가 필요하다.
이 함수는 노드가 유망한지 판단하는 데 사용된다.

1
2
3
4
5
def is_valid(state):
    # 문제의 제약 조건을 검사하는 로직
    # 예: N-Queens 문제에서 퀸들이 서로 공격하지 않는지 확인
    # 제약 조건을 모두 만족하면 True, 아니면 False 반환
    pass

백트래킹 함수(Backtracking Function)
상태 공간 트리를 재귀적으로 탐색하는 핵심 함수이다.
일반적인 구조는 다음과 같다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def backtrack(state):
    # 종료 조건: 완전한 해답인지 확인
    if is_complete(state):
        process_solution(state)
        return

    # 다음 가능한 모든 선택 생성
    for next_choice in generate_choices(state):
        # 선택이 유효한지 확인(가지치기)
        if is_valid(state + next_choice):
            # 선택을 상태에 추가
            apply_choice(state, next_choice)
            # 재귀적으로 다음 단계 탐색
            backtrack(state)
            # 백트래킹: 선택 취소
            remove_choice(state, next_choice)

상태 공간 트리 최적화 전략

상태 공간 트리를 효율적으로 탐색하기 위한 몇 가지 최적화 전략이 있다:

가지치기(Pruning) 최적화
가능한 한 일찍 유망하지 않은 노드를 식별하여 불필요한 탐색을 줄이는 것이 중요하다.
이를 위해 강력한 유효성 검사 함수를 개발해야 한다.
변수 순서 최적화(Variable Ordering)
어떤 순서로 변수를 선택하는지도 중요하다.
일반적으로 가장 제약이 많은 변수(가능한 값이 적은 변수)부터 결정하는 것이 효율적이다.
이를 “최소 잔여 값(Minimum Remaining Values, MRV)” 휴리스틱이라고 한다.
값 순서 최적화(Value Ordering)
변수에 할당할 값의 순서도 중요하다.
다른 변수에 가장 적은 제약을 가하는 값부터 시도하는 것이 좋다.
이를 “최소 제약 값(Least Constraining Value, LCV)” 휴리스틱이라고 한다.
전방 검사(Forward Checking)
변수에 값을 할당할 때마다 다른 변수의 도메인(가능한 값의 집합)을 업데이트하여 불일치를 조기에 감지한다.
아크 일관성(Arc Consistency)
더 강력한 일관성 검사 기법으로, 두 변수 간의 제약 조건을 만족하는 값의 조합만 유지한다.

상태 공간 트리 예시

부분집합 문제

부분집합 문제(Subset Sum Problem)를 통해 상태 공간 트리를 구체적으로 설명해보자.
이 문제는 주어진 집합에서 원소들의 합이 특정 값이 되는 부분집합을 찾는 문제이다.

예를 들어, 집합 {1, 2, 3, 4}에서 합이 6이 되는 부분집합을 찾는 문제를 생각해보자.

상태 공간 트리 구성

루트 노드: 초기 상태 (아무 원소도 선택하지 않은 상태, 합 = 0)
내부 노드: 일부 원소를 선택한 상태 (예: {1, 2} 선택, 합 = 3)
리프 노드: 모든 원소에 대해 선택 여부를 결정한 상태
간선: 각 원소를 선택하거나 선택하지 않는 결정

이 문제의 상태 공간 트리는 다음과 같이 시각화할 수 있다:

1
2
3
4
5
6
7
                        Root(합=0)
                      /           \
                 선택1             미선택1
                 /    \           /    \
           선택1,2   선택1,미선택2  미선택1,선택2  미선택1,미선택2
             / \        / \          / \          / \
            …        …          …          …

각 레벨은 특정 원소의 선택 여부를 결정한다.
루트에서 리프까지의 경로는 모든 원소에 대한 선택 집합을 나타낸다.

백트래킹 과정

루트 노드에서 시작한다.
첫 번째 원소(1)를 선택하는 경로로 진행한다. (현재 합: 1)
두 번째 원소(2)를 선택하는 경로로 진행한다. (현재 합: 3)
세 번째 원소(3)를 선택하는 경로로 진행한다. (현재 합: 6)
- 이 시점에서 합이 6이 되어 해답을 찾음! 해답: {1, 2, 3}
그 외에도 다른 경로를 탐색하여 합이 6이 되는 부분집합을 모두 찾을 수 있다. (예: {1, 2, 3}, {2, 4}, {1, 5})

가지치기 예시

만약 현재까지의 합이 목표값(6)을 이미 초과한 경우, 그 노드는 유망하지 않다.
예를 들어, {1, 2, 4}를 선택한 상태(합: 7)에서는 더 이상 진행할 필요가 없으므로 백트래킹한다.

N-Queens 문제

N-Queens 문제는 NxN 크기의 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제이다.
4-Queens 문제(4x4 체스판에 4개의 퀸 배치)를 예로 들어보자.

상태 공간 트리 구성

루트 노드: 빈 체스판 (아직 퀸을 배치하지 않은 상태)
내부 노드: 일부 행에 퀸을 배치한 상태
리프 노드: 모든 행에 퀸을 배치한 상태
간선: 특정 행의 특정 열에 퀸을 배치하는 결정

이 문제의 상태는 현재까지 배치된 퀸들의 위치이다.
백트래킹 알고리즘은 한 행에 하나의 퀸만 배치할 수 있다는 점을 활용하여 상태 공간을 크게 줄일 수 있다.

백트래킹 과정

첫 번째 행의 첫 번째 열에 퀸을 배치한다.
두 번째 행에 퀸을 배치할 수 있는 유효한 위치(첫 번째 행의 퀸과 충돌하지 않는 위치)를 찾는다.
유효한 위치를 찾으면 그곳에 퀸을 배치하고 다음 행으로 진행한다.
만약 유효한 위치가 없다면, 이전 행으로 돌아가(백트래킹) 다른 위치를 시도한다.
모든 행에 퀸을 성공적으로 배치하면 해답을 찾은 것이다.

가지치기 예시

첫 번째 행의 첫 번째 열에 퀸을 배치한 후, 두 번째 행의 첫 번째 열은 같은 열에 있으므로 유효하지 않다.
또한 두 번째 행의 두 번째 열은 대각선상에 있으므로 유효하지 않다. 따라서 이러한 상태들은 바로 가지치기 된다.

실제 코드에서의 상태 공간 트리

4-Queens 문제를 해결하는 Python 코드를 통해 상태 공간 트리의 구현을 살펴보자:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def solve_n_queens(n):
    solutions = []
    
    # 상태: 각 행별 퀸의 열 위치를 저장하는 배열
    # board[i] = j는 i번째 행의 j번째 열에 퀸이 있음을 의미
    board = [-1] * n
    
    def is_valid(row, col):
        # 현재 위치(row, col)에 퀸을 놓을 수 있는지 검사
        for prev_row in range(row):
            prev_col = board[prev_row]
            
            # 같은 열에 있는지 검사
            if prev_col == col:
                return False
            
            # 대각선에 있는지 검사
            if abs(prev_row - row) == abs(prev_col - col):
                return False
        
        return True
    
    def backtrack(row):
        # 모든 행에 퀸을 배치했으면 해답 추가
        if row == n:
            solutions.append(board[:])
            return
        
        # 현재 행의 각 열에 퀸 배치 시도
        for col in range(n):
            if is_valid(row, col):  # 가지치기: 유효한 위치인지 검사
                # 상태 변경: 퀸 배치
                board[row] = col
                # 다음 행으로 재귀 호출
                backtrack(row + 1)
                # 백트래킹: 퀸 제거 (명시적으로 코드에 나타내기 위해 작성, 다음 반복에서 덮어씌워짐)
                board[row] = -1 
    
    # 첫 번째 행부터 시작
    backtrack(0)
    return solutions

이 코드에서:

상태: board 배열이 현재 상태를 나타낸다.
상태 전이: 퀸을 특정 위치에 배치하는 결정(board[row] = col)이 상태 전이이다.
유효성 검사: is_valid 함수가 현재 위치에 퀸을 배치할 수 있는지 검사한다.
가지치기: 유효하지 않은 위치는 더 이상 탐색하지 않는다.
백트래킹: 현재 행의 모든 열을 시도한 후 이전 행으로 돌아간다.

이해

체스에서 퀸은 가로, 세로, 대각선으로 이동할 수 있다.
따라서:

같은 행에 퀸이 있으면 안 된다.
같은 열에 퀸이 있으면 안 된다.
같은 대각선에 퀸이 있으면 안 된다.

먼저 기본 개념을 이해해 보면:

board[i] = j는 i번째 행의 j번째 열에 퀸이 있다는 의미.
예를 들어 [1, 3, 0, 2]는 0행 1열, 1행 3열, 2행 0열, 3행 2열에 각각 퀸이 있다는 의미.

4-Queens 시각화 예시

1
2
3
4
5
6
  0 1 2 3 (열)
0 □ □ □ □
1 □ □ □ □
2 □ □ □ □
3 □ □ □ □
(행)

첫 번째 시도: 백트래킹 과정 시각화
시작: board = [-1, -1, -1, -1] (모든 행에 퀸이 배치되지 않은 상태)
1. 단계 1: 첫 번째 행(row=0)에서 시작
  - col=0에 퀸 배치 시도: 유효함 → board = [0, -1, -1, -1]
  1 2 3 4 5
  0 1 2 3 0 Q □ □ □ 1 □ □ □ □ 2 □ □ □ □ 3 □ □ □ □
2. 단계 2: 두 번째 행(row=1)으로 진행
  - col=0에 퀸 배치 시도: 같은 열에 있어 유효하지 않음
  - col=1에 퀸 배치 시도: 대각선에 있어 유효하지 않음
  - col=2에 퀸 배치 시도: 유효함 → board = [0, 2, -1, -1]
  1 2 3 4 5
  0 1 2 3 0 Q □ □ □ 1 □ □ Q □ 2 □ □ □ □ 3 □ □ □ □
3. 단계 3: 세 번째 행(row=2)으로 진행
  - 모든 열에 대해 퀸 배치 시도: 어떤 위치도 유효하지 않음
  - 백트래킹: 두 번째 행의 퀸 위치 변경
  1 2 3 4 5
  0 1 2 3 0 Q □ □ □ 1 □ □ □ □ (두 번째 행의 퀸 제거) 2 □ □ □ □ 3 □ □ □ □
  - col=3에 퀸 배치 시도: 유효함 → board = [0, 3, -1, -1]
  1 2 3 4 5
  0 1 2 3 0 Q □ □ □ 1 □ □ □ Q 2 □ □ □ □ 3 □ □ □ □
4. 단계 4: 다시 세 번째 행(row=2)으로 진행
  - col=1에 퀸 배치 시도: 유효함 → board = [0, 3, 1, -1]
  1 2 3 4 5
  0 1 2 3 0 Q □ □ □ 1 □ □ □ Q 2 □ Q □ □ 3 □ □ □ □
5. 단계 5: 네 번째 행(row=3)으로 진행
  - 모든 열에 대해 퀸 배치 시도: 어떤 위치도 유효하지 않음
  - 백트래킹: 세 번째 행의 퀸 위치 변경

… (이런 식으로 계속)

상태 공간 트리의 시간 및 공간 복잡도

상태 공간 트리의 크기와 탐색 비용은 문제의 특성과 가지치기 효율성에 따라 크게 달라진다.

시간 복잡도
- 최악의 경우: 가지치기 없이 전체 트리를 탐색하는 경우, 시간 복잡도는 O(b^d)이다. 여기서 b는 각 노드의 평균 분기 계수(branching factor), d는 트리의 깊이이다.
- 평균/최선의 경우: 효율적인 가지치기를 통해 탐색 공간을 크게 줄일 수 있지만, 정확한 분석은 문제와 구현에 따라 다릅니다.
  예를 들어, N-Queens 문제에서 가지치기 없이는 N^N개의 경우의 수를 검사해야 하지만, 백트래킹을 사용하면 훨씬 적은 수의 노드만 탐색하면 된다.
공간 복잡도
- 재귀를 사용하는 백트래킹 알고리즘의 공간 복잡도는 주로 재귀 스택의 깊이에 의해 결정된다. 일반적으로 O(d)이다(d는 트리의 깊이).

상태 공간 트리를 사용하는 다양한 문제들

상태 공간 트리는 다양한 문제에 적용될 수 있다:

조합 최적화 문제: 외판원 문제(TSP), 배낭 문제(Knapsack) 등
제약 만족 문제: N-Queens, 스도쿠, 십자말풀이 등
게임 트리: 체스, 오목, 틱택토 등의 게임에서 최선의 수를 찾는 문제
그래프 알고리즘: 해밀턴 경로, 그래프 색칠 문제 등

상태 공간 트리를 효과적으로 시각화하는 방법

상태 공간 트리를 시각화하면 알고리즘을 더 잘 이해하고 디버깅하는 데 도움이 된다:

그래프 시각화 도구: Graphviz, NetworkX+Matplotlib 등을 사용하여 트리 구조를 시각화
로깅: 각 노드 방문과 백트래킹 시점을 로그로 남겨 탐색 과정 추적
단계별 애니메이션: 상태 변화를 애니메이션으로 표현하여 알고리즘의 진행 과정 시각화