[알고리즘] 언제 BFS를, DFS를 써야할까?

들어가기 전에, 아주 짧은 요약을 해 보자면

BFS는 해당 노드 주변을 중심으로 조사하고

DFS는 해당 노드의 끝까지 파고드는 느낌으로 생각하시면 좋습니다.

---

다음은 아래의 글을 번역했습니다.

stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

- 그렇게 깊지 않고 해답이 트리의 뿌리에서 그닥 떨어져 있지 않다는걸 알면 BFS를 쓰세요.

 

- 트리의 깊이가 상당히 깊은데 해답이 몇 개 없다면 DFS를 사용하는 방법은 깊이를 전부 다 서치하므로 시간이 엄청나게 걸릴거라 BFS가 낫습니다.

 

- 트리가 깊다기보다 엄청나게 넓으면 BFS의 사용은 메모리를 상당히 잡아먹을 것 입니다. 때문에, BFS의 사용은 실용적이지 못할 거에요.

 

- 해답들이 많지만 트리의 깊숙한 곳에 있다면 BFS는 실용적이지 못할 것 입니다.

 

- 트리가 엄청 깊으면 깊이를 제한하는 것도 필요할 것 입니다.

 

물론 말이 그렇다는거지 일단 경험해보셔야 알 겁니다.

 

---

결국 결론은 

1. 해당 트리가 깊은가 

2. 해당 트리가 넓은가

에서 나뉘는 것 같네요.

DFS와 BFS를 접하고 개념의 감을 잘 잡게 해 준 것 같습니다.