DFS / BFS 차이

두가지 모두 그래프를 탐색하는 방법이다.

 

DFS

가장 깊은 곳까지 탐색을 마치고 돌아와서 탐색하는 방법. 예를들면 미로찾기를 할 때 한 방향으로 쭉 가고, 막다른 길이 나오면 다시 가장 가까운 갈림길로 돌아와서 다시 그 방향으로 쭉 가는 방법. 

특징)

1. DFS는 모든 노드를 방문해야할 때 사용하면 좋다.★★★ (다만, 모든 정점을 방문할 땐 DFS나 BFS나 편한걸 사용하면 되지만 DFS의 코드가 더 짧아서 보통 DFS를 추천하고, 속도는 BFS가 더 빨라서 제한시간이 빡세게 잡혀있다면 BFS를 사용하는게 좋은 경우도 있다.)
2. DFS는 Stack 또는 재귀함수를 사용하는데 보통은 스택을 사용하길 권장한다.★
3. 경로마다 특징이 있는 경우 DFS를 사용해야한다.
4. 탐색할 그래프가 엄청 크다면 DFS를 사용한다.

---

BFS

가장 가까운 곳을 먼저 방문하고, 멀리 떨어져 있는 곳을 나중에 방문하는 식. DFS는 멀리 있더라도 길이 이어져 있으면 그냥 쭉 가는 반면, BFS는 가까운 길부터 먼저 방문함.

특징)

1. BFS는 최단거리를 구해야할 때 유용하다.★★★
2. BFS는 Queue를 사용하여 구현한다.

 

BFS와 DFS의 차이