백트래킹
백트래킹 (Backtracking)
백트래킹(Backtracking)은 문제 해결을 위해 가능한 모든 경우의 수를 탐색하되, 특정 경로가 더 이상 해가 될 가능성이 없다고 판단되면 그 즉시 되돌아가 다른 경로를 탐색하는 알고리즘 기법입니다. 깊이 우선 탐색(DFS)을 기반으로 불필요한 탐색을 줄이는 가지치기(Pruning)가 더해진 전략으로, 모든 해를 찾거나 최적해를 찾는 문제에 널리 사용됩니다.
👣 백트래킹의 동작 원리
백트래킹은 문제의 해를 찾는 과정을 '상태 공간 트리(State Space Tree)' 탐색으로 간주합니다. 트리의 각 노드는 해를 구성하는 과정의 '상태'를 나타냅니다.
1. 루트에서 시작하여 깊이 우선 탐색(DFS) 방식으로 잠재적인 해를 탐색합니다. 2. 탐색을 진행하다가, 현재 경로가 더 이상 유망하지 않다(non-promising)고 판단되거나 제약 조건에 위배되면, 그 경로(서브트리)에 대한 탐색을 중단합니다. 3. 부모 노드로 되돌아가(backtrack), 아직 시도하지 않은 다른 선택지를 선택하고 탐색을 계속합니다. 4. 이 가지치기(Pruning)를 통해, 모든 경우를 탐색하는 완전 탐색(Brute-force)보다 훨씬 효율적으로 해를 찾을 수 있습니다.
🆚 다른 알고리즘과의 비교
- 깊이 우선 탐색 (DFS)과의 관계
> * 백트래킹은 DFS를 기반으로 동작합니다. 하지만 DFS가 단순히 모든 경로를 방문하는 것이 목적이라면, 백트래킹은 '가지치기'를 통해 불필요한 탐색을 줄여 효율성을 높이는 데 중점을 둡니다.
- 동적 계획법 (DP)과의 차이
> * DP : 문제에 '중복되는 부분 문제(Overlapping Subproblems)'가 존재할 때, 그 결과를 저장(메모이제이션)하여 재사용합니다. > * 백트래킹 : 중복되는 부분 문제가 없을 수 있으며, 주로 결정, 최적화, 나열 등 다양한 종류의 '제약 만족 문제(Constraint Satisfaction Problems)'를 푸는 데 사용됩니다.
💡 개발자 핵심 Point
- 백트래킹은 주로 재귀 함수를 사용하여 구현됩니다.
- 유망성 판단 (Promising Check) : 재귀 함수의 각 단계에서, 현재까지의 선택이 제약 조건을 만족하며 앞으로 해가 될 가능성이 있는지를 검사하는 함수를 구현하는 것이 백트래킹 알고리즘의 핵심입니다.
- 대표적인 백트래킹 문제
> * N-Queens 문제 : N x N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. > * 미로 찾기 / 스도쿠 풀이 : 가능한 모든 경로/숫자를 시도해보다가, 막히면 되돌아와 다른 경로/숫자를 시도합니다. > * 조합/순열/부분집합 구하기 : 특정 조건을 만족하는 모든 조합/순열/부분집합을 찾는 문제입니다.
