[algorithm]backtracking
Backtracking
정답을 찾는 도중 정답 아니어서 막히면, 되돌아가서 다시 정답을 찾아가는 기법. 최적화 문제와 결정 문제를 푸는 방법.
DFS와 Backtracking
- DFS
모든경로를 탐색하는 방법. 불필요한 경로를 사전에 차단하는 행동이 없으므로 경우의 수를 줄이지 못함. - Backtracking(가지치기)
경로를 탐색하는 도중, 정답이 아닌것 같으면 더이상 가지 않고 되돌아감. 반복을 줄일 수 있다.
정리
백트래킹은 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는것.
사용하는 경우: DFS등의 모든 경우의 수를 탐색하는 과정에서 조건문을 걸어 답이 될 수 없는 상황을 정의하고 조건에 부합하면 탐색을 중지하고 다른 경우를 탐색한다.