백트래킹 vs DFS

알고리즘 문제를 풀다보면 DFS인 것 같은데 백트래킹으로 분류된 문제들이 있다.

헷갈린 부분이 있어서 이번 기회에 확실히 정리를 하고 넘어가고자 한다.

---

* DFS (깊이 우선 탐색)

가능한 모든 경로를 다 탐색한다. 따라서, 불필요한 경로도 무조건 끝까지 탐색을 하기 때문에 경우의 수를 줄이지는 못한다.

 

* 백트래킹 (Back-tracking)

답을 찾아가는 도중, 지금의 경로가 답이 될 것 같지 않으면 더이상 진행하지 않고 윗단계로 되돌아간다.

이를 가지치기라고 하는데, 불필요한 경우의 수를 줄일 수 있으므로 시간복잡도를 개선할 수 있다.

---

문제풀이에서는 DFS로 모든 경우의 수를 완전탐색하는 과정 중에 조건문을 걸어서 답이 절대로 나올 수 없는 상황을 정의하고, 해당이 되면 탐색 중단 후 그 이전으로 돌아가서 다른 자식노드를 탐색하도록 구현한다.