[이진탐색] 깊이 우선 탐색[DFS]과 백트래킹[Backtracking] 차이점

DFS와 Backtracking의 차이점을 알아보자.

 

 

DFS

 

완전 탐색을 기본으로 하는 그래프 순회 기법으로 가능한 모든 경로를 탐색한다.

불필요한 경로를 사전에 차단하는 행동이 없다. 따라서 자원 소모가 심하다.

 

 

Backtracking

 

경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로가 갔다면 더 가지 않고 되돌아온다.

이는 가지치기라고 불린다.

 

불필요한 경로를 조기 차단하기 때문에 확인해야 하는 경로 수를 줄일 수 있다.

 

 

---

 

 

 

 

위와 같은 트리가 있다. ALT라는 단어를 찾아보자.

 

 

 

 

 

DFS는 ALT라는 단어를 찾기 전까지 모든 노드를 방문한다. 

Backtracking은 ALT라는 단어를 찾는 과정에서 ALT라는 단어가 될 수 없을 것 같은 경로에 갔다면 더 가지 않고 돌아온다.