Backtracking
- 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법
- 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
- 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색함
- 최적화 문제와 결정 문제를 푸는 방법이 됨
DFS & Backtracking
- DFS
- 가능한 모든 경로를 탐색함
- Backtracking
- 해를 찾아가는 도중, 지금 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아감
- 노드가 유망한지 판단하고 유망하지 않으면 가지차기하는 것
- 유망하다(promising) = 해가 될 가능성이 있다
- 가지치기(pruning) = 유망하지 않은 노드에 가지 않는다
- 가지치기를 얼마나 잘 하느냐에 따라 효율성이 결정됨
참고
