개념
백트래킹(Backtracking) 알고리즘은 조합적 문제나 순열 문제 등에서 가능한 모든 해를 탐색하는 알고리즘입니다. 이 알고리즘은 완전 탐색(Exhaustive Search)의 한 형태로, 모든 가능한 경우를 시도하면서 해를 찾는 방식입니다.
동작 방식
-
선택(선정) 단계: 문제에서 선택해야 하는 요소 중 하나를 선택합니다. 이 선택은 후보 요소들 중에서 이루어집니다. 선택은 보통 재귀 호출의 인자로 전달되며, 탐색의 한 단계를 의미합니다.
-
제약 조건 확인: 선택된 요소에 대해 현재 상태에서 만족해야 하는 제약 조건을 확인합니다. 이 조건은 문제에 따라 다르며, 일반적으로는 유효성 검사를 의미합니다. 만약 제약 조건을 만족하지 않는다면, 해당 선택은 유망하지 않으므로 중단됩니다.
-
해 검증: 선택된 요소들이 문제의 해를 구성하는지 검증합니다. 해 검증은 일부 문제에서만 필요하며, 문제에 따라 검증 방법이 다를 수 있습니다.
-
해 발견: 선택된 요소들이 제약 조건을 만족하고 문제의 해를 구성한다면, 이는 유효한 해입니다. 이러한 해를 발견했을 때, 해당 해를 저장하거나 출력하고, 추가적인 해를 탐색하지 않도록 종료합니다.
-
재귀 호출: 선택, 제약 조건 확인, 해 검증을 거쳐 해 발견이 되지 않았다면, 다음 선택을 진행하기 위해 재귀 호출을 수행합니다. 재귀 호출은 선택의 단계를 한 단계씩 진행하며, 모든 가능한 선택지에 대해 탐색을 수행합니다.
-
백트래킹(되돌아가기): 재귀 호출이 끝난 후, 현재 선택의 단계에서의 모든 선택지에 대한 탐색이 완료되었거나 유효한 해를 발견한 경우, 이전 선택의 단계로 되돌아갑니다. 이 과정을 백트래킹이라고 합니다. 백트래킹을 통해 다음 선택지로 넘어갈 수 있도록 되돌아갑니다.
특징
-
깊이 우선 탐색(Depth-First Search, DFS) 기반: 백트래킹은 주로 깊이 우선 탐색을 기반으로 구현됩니다. 한 가지 선택을 하고 해당 선택으로부터 가능한 모든 경우를 탐색하며, 해결책을 찾을 때까지 계속해서 깊이를 탐색합니다.
-
가능성 있는 해를 탐색: 백트래킹은 가능성 있는 해를 탐색하는 방법입니다. 여러 선택지 중에서 하나를 선택하고, 선택한 경우의 제약 조건을 검사하여 유효한 해의 가능성을 확인합니다. 유효한 해의 가능성이 없는 경우, 더 이상 탐색을 진행하지 않고 이전 단계로 되돌아갑니다.
-
가지치기(Pruning): 백트래킹은 가지치기를 통해 비효율적인 탐색을 줄입니다. 유효한 해의 가능성이 없는 경우에는 해당 선택지를 폐기하고, 다른 선택지로 진행하는 것을 의미합니다. 이로써 탐색 과정에서 필요없는 분기를 제거하여 시간과 공간을 절약할 수 있습니다.
-
상태 공간 트리(State Space Tree) 탐색: 백트래킹은 문제를 해결하기 위한 모든 가능한 상태의 조합을 나타내는 상태 공간 트리를 탐색합니다. 각 노드는 선택의 단계를 나타내며, 이를 따라 탐색을 진행하면서 해를 찾거나 유효하지 않은 경로를 제외합니다.
-
재귀적 구현: 백트래킹은 보통 재귀적으로 구현됩니다. 재귀 호출을 통해 선택 단계를 진행하고, 제약 조건을 검사하고, 해를 발견하거나 백트래킹하여 이전 단계로 되돌아갑니다. 이는 코드의 간결성과 가독성을 높여주는 장점이 있습니다.
-
추가적인 메모리 공간 사용: 백트래킹은 상태 공간 트리를 탐색하기 위해 재귀 호출 스택을 사용합니다. 따라서 큰 입력에 대해서는 스택의 크기가 커질 수 있으며, 이는 추가적인 메모리 공간을 필요로 합니다.
예시
예시를 위해 순열 생성 문제를 생각해 보겠습니다. 주어진 N개의 숫자로 가능한 모든 순열을 생성하는 문제입니다.
1. 초기 상태:
- 주어진 숫자: [1, 2, 3]
- 현재 생성된 순열: []
2. 첫 번째 숫자 선택:
- 후보군: [1, 2, 3]
- 현재 생성된 순열: [1]
1을 선택한 후, 다음 숫자를 선택하기 위해 재귀 호출을 수행합니다.
3. 두 번째 숫자 선택:
- 후보군: [2, 3]
- 현재 생성된 순열: [1, 2]
2를 선택한 후, 다음 숫자를 선택하기 위해 재귀 호출을 수행합니다.
4. 세 번째 숫자 선택:
- 후보군: [3]
- 현재 생성된 순열: [1, 2, 3]
3을 선택한 후, 순열이 완성되었으므로 결과를 저장하거나 출력합니다.
5. 세 번째 숫자 선택 시 후보군이 더 이상 없으므로, 이전 단계로 돌아갑니다.
6. 두 번째 숫자 선택 시 후보군에 남은 숫자가 없으므로, 이전 단계로 돌아갑니다.
7. 첫 번째 숫자 선택 시 후보군에 남은 숫자가 없으므로, 이전 단계로 돌아갑니다.이렇게 이전 단계로 돌아가면서 다른 후보군을 선택하면서 모든 가능한 순열을 생성하게 됩니다. 백트래킹 알고리즘은 해를 찾기 위해 가능한 모든 경우를 탐색하므로 시간이 오래 걸릴 수 있지만, 조건을 만족하는 해를 찾을 수 있습니다.
