너비 우선 탐색(BFS) vs 깊이 우선 탐색(DFS)

일단, 둘을 다음 그림을 통해 이해해보자.

출처 https://namu.wiki/w/BFS

 

 

너비 우선 탐색(BFS)

---

특징

• depth는 0이 아닌 1부터 시작
• 노드 수가 적고 깊이가 얕은, 검색 대상의 규모가 작은 경우, 유리하다.
• 큐 이용

장점

• 답이 되는 경로가 여러 개인 경우에, 최단 경로를 보장한다.
• 최단 경로가 존재하면, 어느 한 경로가 무한히 깊어진다 하더라도, 최단 경로를 반드시 찾을 수 있다.

단점

• DFS에 비해 저장 공간의 필요성이 크다. DFS와는 달리 큐를 이용해서 다음에 탐색할 노드를 저장하므로, 노드의 수가 많을수록 필요 없는 노드들까지 저장해야 하기 때문이다. 
• 최악의 경우에는 모든 경로를 다 살펴봐야 한다.

 

 

 

깊이 우선 탐색(DFS)

---

특징

• depth는 0이 아닌 1부터 시작
• 검색 대상의 규모가 클 경우, 유리하다.
• 재귀, 스택 이용

장점

• 하나의 노선을 끝까지 들어가서 탐색하기 때문에, 운이 좋으면, 단 몇 번만에 경로를 찾을 수 있다.
• 하나의 노선을 끝까지 들어가기 전에, 찾으려는 노드가 존재하지 않음을 미리 체크할 수 있다면, 그 순간 바로 다음 탐색으로 넘어갈 수 있다.
• BFS보다 탐색 시간이 조금 오래 걸릴지라도, 모든 노드를 완전히 탐색할 수 있다.
• BFS에 비해 저장 공간의 필요성이 적다. 백트래킹을 해야 하는 노드들만 저장해주면 되기 때문이다.
• 찾아야 하는 노드가 깊은 단계일수록, 좌측에 있을수록 BFS보다 유리하다.

단점

• 운이 안좋으면, 모든 경로를 탐색하고 나서야, 찾으려는 노드를 찾을 수 있으므로, 시간이 가장 오래 걸릴 수도 있다.
• 찾은 경로가 최단 경로라는 보장은 없다.