BFS, DFS 두가지 모두 그래프를 탐색하는 방법이다.
| DFS(깊이우선탐색) | BFS(너비우선탐색) |
|---|---|
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
DFS 깊이 우선 탐색 (Depth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림
BFS 너비 우선 탐색 (Breadth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택함
※ DFS와 BFS의 시간 복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만 일반적으로 DFS를 재귀 함수로 구현한다는 점에서 DFS보다 BFS가 조금 더 빠르게 동작한다고 기억하면 된다.
N이 노드의 개수, E가 간선의 개수일 때
인접 리스트: O(N + E)
인접 행렬: O(N^2)
→ 일반적으로 인접 리스트 방식이 더 효율적이다.
DFS와 BFS를 활용한 문제 유형/응용
- 그래프의 모든 정점을 방문하는 것이 주요한 문제
- 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 무방
- 경로의 특징을 저장해둬야 하는 문제
- 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못한다.)
- 최단거리 구해야 하는 문제
- 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리하다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.
- 검색 대상 그래프가 정말 크다면 DFS를 고려. 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
출처
https://velog.io/@lucky-korma/DFS-BFS의-설명-차이점
https://sunho-doing.tistory.com/entry/알고리즘-탐색-알고리즘-DFS-BFS
