DFS와 백트래킹
깊이 우선 탐색(DFS)
- DFS는 가능한 모든 경로(후보)를 탐색한다.
=>따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.
백트래킹(Backtracking)
- 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다.
- 코딩에서는 반복문의 횟수를 줄일 수 있어 효율적이다.
- 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 => 가지치기
=>가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다.
정리
백트래킹 기법의 유망성 판단
해가 될 가능성이 있다면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)한다.