DFS와 백트래킹

 참고 링크 : https://chanhuiseok.github.io/posts/algo-23/

 백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

 최적화 문제와 결정 문제를 푸는 방법이 된다.

 

---

DFS (깊이 우선 탐색) : 가능한 모든 경로(후보) 탐색. 경우의 수를 줄이지 못함 ( 최적화 문제에 부적합 )

 

백트래킹 : 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 탐색 x

 

예시로 최대 / 최솟값을 찾는 문제에서 MAX_VALUE , MIN_VALUE 등을 두고 탐색 중 MIN_VALUE 보다 크면 최솟값이 될 수 없으므로 탐색을 중단하고 뒤로 돌아가는 식으로 구현할 수 있겠다.

 

---

문제풀이에서는 DFS등으로 모든 경우의 수를 탐색하는 과정에서 조건문등을 걸어 상황을 정의하고, 해당 상황일 경우 탐색을 중지한 뒤 그 이전으로 돌아가 다른 경우를 탐색하게끔 구현. (안될놈은 미리 가지치기를 한다)