[자료 구조/알고리즘] 백트래킹

백트래킹(backtracking)(또는 역추적) 알고리즘이란 최적의 해결책을 찾기 위해 모든 가능한 방법을 후보(candidate)로 구성한 후, 점진적으로 후보들을 시도하면서 유효한 후보가 아닐 경우(문제의 정답 조건을 만족하지 않을 경우) 문제 해결 과정에서 제외하고 되돌아가 다른 후보를 시도(백트랙)하는 과정을 반복하며 문제를 해결해 나가는 알고리즘이다. 후보를 문제 해결 과정에서 제외하는 것을 가지치기(pruning)이라고 한다.

백트래킹의 핵심은 문제를 해결하는 과정에서 점진적으로(incrementally) 부분적인(partial) 해결책을 구성하는 것이다. 부분적인 해결책들을 확장해서 또다른 부분적인 해결책들을 구성해 나가면서 최적의 해결책을 찾는다. 부분적인 해결책이 끝까지 확장된 것을 정답으로 간주한다. 부분적인 해결책이 문제의 사전 정의된 제약 조건(constraint)을 만족하지 않는 경우 해당 해결책을 더 이상 확장할 필요가 없다고 판단하고 해결책 확장 과정을 중단하며(가지치기), 다른 해결책을 시도한다(백트랙).

해결책을 부분적으로 구성 및 확장한다는 개념, 즉 부분적인 해결책이 서로 연결되어 있다는 개념을 사용하므로 그래프 자료 구조를 사용하며, 바로 이전의 해결책으로 되돌아가서 다른 해결책을 시도하기 위해 그래프 탐색 알고리즘 중 하나인 깊이 우선 탐색을 사용한다. 일단 한 경로를 가능한 깊이까지 끝까지 탐색하며 정답을 찾으려고 시도한 후 더 이상 갈 곳이 없으면(정답이 아니거나 해당 경로에서는 더 이상 정답을 찾을 가능성이 없다고 판단되면) 되돌아와서(백트랙) 시도해보지 않은 다른 경로를 탐색한다.

백트래킹은 정답을 찾을 때까지 모든 경로를 탐색해 나가므로 부르트 포스 접근(brute-force approach)과 유사하지만, 백트래킹은 가지치기 과정을 통해 경로 탐색 시도 횟수를 줄이는 최적화 과정을 포함한다. 부르트 포스 방법은 문제 해결 과정 중에 정답을 찾더라도 중단하지 않고 모든 경로를 시도하는 반면, 백트래킹은 현재 경로가 더 이상 정답으로 이어지지 않는 경로라고 판단되면 해당 경로의 탐색을 더이상 진행하지 않고 되돌아가 다른 경로를 탐색한다. 즉, 불필요한 탐색 과정을 제거하여 문제 해결 과정의 효율성을 높인다. 부르트 포스 방법은 구현이 간단하지만 경우의 수가 많을 경우 시간이 많이 소요되어 비효율적인 반면, 백트래킹 방법은 최적화를 통해 모든 경우의 수를 다 탐색하지 않아 효율적인 반면, 문제의 사전 정의된 조건을 정확히 분석하여 백트랙 및 가지치기해야 하므로 구현이 보다 복잡하다.

백트래킹 알고리즘은 문제를 해결하기 위해 모든 가능성을 탐색하는 문제에서 주로 사용된다. 예를 들어 미로에서 목적지까지의 길을 찾는 문제의 경우 길을 찾다가 막다른 골목에 도달하면 이전 분기 지점으로 되돌아가 다시 길을 찾는 방법을 목적지까지 도달할 때까지 반복한다. 백트래킹을 사용하여 해결할 수 있는 문제의 다른 예로는 수도쿠 퍼즐, 크로스워드 퍼즐 문제, 배낭 채우기 문제, 네트워크 최적화 문제, 순열/조합 문제 등이 있다.

백트래킹은 상태 공간 트리(state-space tree)라는 탐색 트리를 사용하여 모든 가능성을 탐색한다. 상태 공간 트리란 문제에 대한 모든 가능한 상태들을 트리 자료 구조로 표현한 것이다. 상태 공간 트리의 노드는 문제의 부분적인 상태를 나타내며, 노드를 연결하는 간선은 상태 간 변환 또는 전이를 나타낸다. 루트 노드는 초기 상태, 문제의 정답에 해당하는 리프 노드는 최종 상태가 된다. 최종 상태가 바로 문제의 정답이다. 상태 공간 트리는 문제의 정답에 대한 모든 가능한 경로를 구조적으로 그래프 자료 구조로 구조화하여 원하는 목표 경로(정답)에 도달하기 위해 일련의 상태 탐색을 가능하게 한다. 백트래킹에서 노드는 부분적인 해결책을 나타내며, 간선은 해결책의 확장 과정을 나타낸다. 노드를 탐색하면서 해당 노드의 상태가 문제의 사전 정의된 제약 조건을 만족하지 않을 경우 부모 노드로 되돌아온 후(백트랙) 다른 하위 노드를 탐색한다.