백트래킹이란?
문제 해결을 위해 가능한 모든 경우의 수를 전부 체계적으로 고려하는 알고리즘을 완전 탐색(Brute-force) 또는 상태 공간 탐색이라고 하며, 이때 상태의 변화를 트리 형태로 표현한 구조를 상태 공간 트리라고 합니다.
대표적인 방식에는 깊이 우선 탐색( Depth First Search, DFS), 너비 우선 탐색(Breadth First Search, BFS), 최선 우선 탐색(Heuristic Search, 휴리스틱 탐색) 등이 있습니다.
특히 모든 경우의 수를 시도해 보는 문제에서는 DFS를 사용하는 것이 구현상 더 간단하고, 백트래킹과도 잘 어울리기 때문에 많이 활용됩니다. BFS도 모든 경우의 수를 탐색할 수는 있지만, 각 단계에서 큐에 많은 상태를 저장해야 하므로 메모리 사용량이 커질 수 있습니다.
단, DFS를 사용할 때 그래프에 순환이 존재하거나 무한 루프에 구조라면, BFS를 사용하는게 좋습니다.
추가로 백트래킹을 이해하기 좋은 문제
- 모든 경우의 수를 나열하는 문제
- 순열 (Permutations): 주어진 원소들을 가능한 모든 순서로 나열하는 문제
- 조합 (Combinations): 주어진 원소들 중에서 특정 개수를 선택하는 모든 경우의 수
- 부분집합 (Subsets): 주어진 집합의 모든 가능한 부분집합을 찾는 문제
- 제약 조건을 만족하는 해를 찾는 문제
- N-Queen 문제, 스도쿠 풀이 등 특정 규칙이나 제약을 모두 만족하는 배열/배치를 찾는 문제.
- 탐험 순서나 결정 순서가 결과에 영향을 미치는 문제