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)가 $a=(a_1,a_2,\cdots ,a_k)$와 같이 존재한다.
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 함수만 바꾸면 원하는 문제를 해결하기 위한 맞춤형 백트래킹 프로그램을 구현할 수 있다.