토픽 21 / 82

백트래킹 (Backtracking)

해를 찾는 도중 막히면 이전 단계로 돌아가(되돌아가기) 다른 경로를 탐색하는 완전 탐색 기반 알고리즘 설계 기법

목적: 모든 가능성 탐색, 제약 만족 문제, 최적해 찾기

특징: 재귀, 되돌아가기(Backtrack), 가지치기(Pruning), DFS 기반

동작: ① 후보 선택 → ② 유망성 검사(promising) → ③ 유망하면 진행, 아니면 백트랙 → ④ 해 찾을 때까지 반복

가지치기(Pruning): 불가능한 경로 조기 차단, 성능 향상

시간 복잡도: 최악 O(2ⁿ) ~ O(n!) - 완전 탐색, 가지치기로 개선

공간 복잡도: O(n) - 재귀 스택

장점: 모든 해 탐색 가능, 제약 만족, 가지치기로 효율 향상

단점: 느림(지수 시간), 최적화 어려움

적용사례: N-Queens, 스도쿠, 미로 탐색, 순열·조합, 부분집합 합, Hamiltonian Path, 그래프 색칠

비교: 백트래킹(완전탐색/가지치기/느림) vs 브루트 포스(전체 탐색/매우 느림) vs 탐욕(빠름/최적 불보장)

연관: DFS, 재귀, N-Queens, 가지치기, 완전 탐색