Backtracking

상위 문서: 알고리즘 설계와 분석

개요

백트래킹은 탐색 공간(search space) 의 모든 가능한 구성을 체계적으로 탐색하는 방법dlek. 하지만 모든 문제에 똑같이 적용되는 알고리즘이 아니라, 각 문제에 맞게 커스터마이징해야 하는 일반적인 틀(general framework)이다. 이때 백트래킹은 결국 암묵적인 상태공간그래프(implicit state-space graph) 를 DFS 방식으로 탐색하는 것과 동일하며, 아래와 같은 특징을 가진다:

1. Subsets/Permutations 탐색에 유용함: 백트래킹은 집합의 모든 부분집합이나 순열을 손쉽게 탐색할 수 있음.
2. 정확성 보장: 가능한 모든 조합을 열거하므로, 누락 없이 정답을 찾을 수 있음.
3. 효율성(Pruning): 단순 DFS보다 효율적으로 하기 위해 “불필요한 가지(dead branches)”를 잘라내야 함.

Sudoku and Backtracking

백트래킹(Backtracking)이란 모든 가능한 해(해답 공간, search space)를 탐색하면서 유망하지 않은 경로는 되돌아가는(recursive pruning)기법이다. 예를 들어 스도쿠를 해결하고자 할때 백트래킹 기법을 사용할 수 있다. 스도쿠는 모든 가능한 숫자 조합을 시도해야 하는 문제이기 때문에, 일종의 완전 탐색(exhaustive search)이 필요하다. 하지만 현실적으로 제약(Constraints) 을 이용하면 불가능한 경우를 일찍 걸러낼 수 있으며, 이러한 과정을 Pruning(가지치기)이라고 한다. 즉, 가능한 경우만 남기고 불가능한 경로는 조기 탈락시켜 효율을 높이는 것이다.

스도코의 문제의 해(각 칸, 혹은 각 열)를 벡터 a로 표기하고, 각 원소 a_i는 해의 i번째 요소를 의미한다고 하자. 이때 각 a_i는 가능한 선택지 집합인 유한 집합 S_i 중 하나에서 선택된다. 이렇게 해를 벡터 형태로 구성하여 가능한 모든 조합을 탐색하는 것이 백트래킹 방식이다. 예를 들어 순열 문제에서는 a_i는 i번째 위치에 올 숫자를 의미한다. 또한 부분집합 문제에서는 a_i는 i번째 원소가 포함되어 있을 경우 true, 아니면 false로 설정된다.

스도쿠 문제를 백트래킹을 통해서 해결하고자 할때는 아래와 같은 절차를 따른다:

1. 부분 해(partial solution)가 [math]\displaystyle{ a = (a_1, a_2, \cdots, a_k) }[/math]와 같이 존재한다.
2. 해를 확장하기 위해서 가능한 후보 a_k+1을 선택한다.
3. 확장된 해가 유효한지(valid) 검사하여 만약 완전한 해이면 저장한다.
   • 아니면, 아직 해가 될 가능성이 있다면 재귀(recursion)적으로 다음 단계를 진행한다.
   • 가능성이 없다면 현재 선택을 “되돌리고(backtrack)” 다른 선택을 시도한다.

즉, “Try → Check → Recur → Undo and Try Next”를 재귀적으로 반복하여 문제를 해결하는 것이 백트래킹의 구조이다.

Backtracking Implementation

아래는 백트래킹의 핵심 알고리즘 구조를 보여주는 수도 코드이다:

Backtrack(a, k)
    if a is a solution, print(a) 
    else {
        k = k + 1
        compute S_k
        while S_k ≠ ∅ do
            a_k = an element in S_k
            S_k = S_k - a_k
            Backtrack(a, k)
    }

위 코드에서 각 변수는 아래와 같다:

• a: 현재까지 만들어진 부분해(partial solution) 벡터
• k: 현재 단계 (몇 번째 요소를 채우는 중인지)
• S_k: 현재 단계에서 가능한 후보(candidate) 집합

위 알고리즘은 아래와 같은 절차를 통해 작동한다:

1. 기저 조건 검사: a가 완전한 해이면 출력(print(a))
2. 아니라면 다음 단계로 확장
   • k를 1 증가 (다음 위치로 이동)
   • 가능한 후보 집합 S_k 계산
   • 후보가 남아 있는 동안 반복:
     1. 하나를 선택해 a_k에 저장
     2. 그 후보를 제외하고 (S_k = S_k - a_k)
     3. 재귀적으로 Backtrack(a, k) 호출

위 절차를 통해서 모든 가능한 조합을 체계적으로 탐색하게 되었다.

Backtracking Implementation on C

아래는 백트래킹 기법을 C언어를 통해서 구현한 것이다:

void backtrack(int a[], int k, data input) {
    int c[MAXCANDIDATES];  /* 후보 집합 */
    int nc;                /* 후보 수 */
    int i;                 /* 반복용 변수 */

    if (is_a_solution(a, k, input)) {
        process_solution(a, k, input);
    } else {
        k = k + 1;
        construct_candidates(a, k, input, c, &nc);
        for (i = 0; i < nc; i++) {
            a[k] = c[i];
            make_move(a, k, input);
            backtrack(a, k, input);
            unmake_move(a, k, input);
            if (finished) return; /* 조기 종료 조건 */
        }
    }
}

아래는 위에서 등장한 함수들에 대한 설명이다:

1. is_a_solution(a, k, input): 현재까지 채운 해가 완전한 해(complete solution) 인지 판단하는 함수이다.
2. construct_candidates(a, k, input, c, nc): 다음 단계에서 시도 가능한 후보들을 생성하는 함수이다.
   • 현재까지 선택된 해 a[1..k-1]을 기반으로 k번째 위치에서 가능한 모든 선택지를 구한다.
   • 후보들은 c 배열에 저장하며, 후보의 개수는 변수 nc에 저장한다.
3. process_solution(a, k): 해를 출력하거나 카운트하거나 저장하는 등, 해를 처리하는 함수이다.

위 코드에서 is_a_solution, construct_candidates, process_solution 함수만 바꾸면 원하는 문제를 해결하기 위한 맞춤형 백트래킹 프로그램을 구현할 수 있다.

Constructing Subsets by Backtracking

해당 문단에서는 어진 집합의 모든 부분집합(2²개)을 백트래킹을 이용해서 생성하는 방법에 대해 설명한다. 즉, {1, 2, 3, …, n} 같은 집합이 있을 때 가능한 모든 조합(포함/비포함)을 탐색하는 문제에 대해서 다룬다. 이를 해결하기 위해서 각 원소 a[i]는 True/False 값을 가지는 크기가 n인 배열 a를 만들 수 있다. 이 경우 하나의 배열 a는 하나의 부분집합을 표현할 수 있다. 예를 들어, a = [True, False, True]는 부분집합 {1, 3}을 의미한다. 이를 백트래킹 표현으로 보면:

1. 각 단계 k마다 후보 집합 S_k = (True,False)
2. 해가 완성되는 시점은 k가 n 이상, 즉 모든 원소에 대해 포함 여부를 결정했을 때이다.

결과적으로 가능한 조합 2ⁿ개가 모두 생선된다.

Subset Generation Tree / Order

Figure는 부분집합을 생성하는 탐색 트리(Generation Tree)를 시각화한 것이다. 해당 트리는 루트에서 시작해서 각 단계마다 “포함한다”또는 “포함하지 않는다”의 두 가지 선택지를 가진다. 이때 트리의 깊이는 집합의 원소 개수 n과 같으며, leaf 노드는 완성된 부분집합을 의미한다.

이러한 원리를 백트래킹 코드에 대해 적용할 수 있다. 이를 위해 아래와 같은 조건을 이해하자:

• 길이가 n인 True/False 벡터를 통해 부분집합을 표현.
• 각 단계의 후보 집합 S_k=(True,False).
• 모든 원소를 처리했을 때 (k == n) → 완성된 해.

Constructing Subsets

이를 아래와 같이 적용할 수 있다:

int is_a_solution(int a[], int k, int n) {
    return (k == n);
}

위는 트리 깊이가 n단계가 되었는지를 확인하여 모든 원소를 처리했는가에 대해서 확인한다.

void construct_candidates(int a[], int k, int n, int c[], int *nc) {
    c[0] = true;
    c[1] = false;
    *nc = 2;
}

각 단계마다 가능한 선택지는 항상 두 가지(True/False)이므로 이에 맞게 설정한다.

void process_solution(int a[], int k, int input) {
    int i;
    printf("{");
    for (i = 1; i <= k; i++) {
        if (a[i] == true) printf(" %d", i);
    }
    printf(" }\n");
}

위는 주어진 모든 부분 집합을 출력하는 코드이다. 이때 출력 대신 다른 검사를 수행하여 알고리즘의 기능을 확장할 수도 있다.

void generate_subsets(int n) {
    int a[NMAX];   /* solution vector */
    backtrack(a, 0, n);
}

위는 전체 프로그램을 실제로 실행시키는 함수이다.

Constructing Permutations by Backtracking

해당 문단에서는 백트래킹 기법을 이용하여 모든 순열을 생성하는 방법에 대해 설명한다. 순열(permutation)이란 n개의 원소를 서로 다른 순서로 배열하는 모든 경우의 수를 의미한다. 예를 들어, {1, 2, 3}의 순열은 123, 132, 213, 231, 312, 321이다. 이때 n개의 원소로 만들 수 있는 순열의 개수는 n!(팩토리얼)이다.

순열을 표현하기 위해서는 a라는 배열을 만들어야 하며, 이때 a[i]는 순열의 i번째 자리에 올 숫자를 나타낸다. 따라서 각 a[i]는 아직 사용되지 않은 숫자 중 하나를 선택해야 한다. 이를 백트래킹 알고리즘의 일반 형태로 표현하면:

[math]\displaystyle{ S_k = \{1, 2, ..., n\} - v }[/math]

즉, 아직 선택되지 않은 원소들의 집합이며, 이에 따라 완전한 해답은 k가 n 이상일 때 얻을 수 있다. Figure 는 순열이 만들어지는 과정을 시각적으로 보여준다. 이는 루트 노드에서 시작하여, 가능한 후보들 중 하나를 선택하며 아래쪽으로 진행함에 따라 더욱 완전한 순열을 만들어 간다. 마지막 leaf 노드들은 완전한 순열들인 {123, 132, 213, 231, 312, 321}을 나타낸다.