DFS & BFS 어떤 것을 쓸까?

DFS

• 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
• 모든 경로를 탐색해야 할 경우 사용에 적합

💡 스택 또는 재귀함수를 통해 구현

BFS

• 루트 노드 또는 임의 노드에서 인저반 노드부터 먼저 탐색하는 방법
• 최소 비용(모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합

💡 큐를 통해 구현

아래와 같은 문제는 DFS, BFS 상관 없이 풀이가 가능함

하지만 길찾기 같은 최단거리(최소 비용)을 구해야 하는 문제에서는 DFS를 쓸 경우 비효율적이므로 시간초과가 뜬다.

결론

DFS는 모든 경로를 탐색하므로 특정 경로를 찾는 경우 BFS보다 느릴 가능성이 높다.

• 모든 경로 탐색 -> DFS
• 특정 경로 탐색 -> BFS