DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.
그래프의 모든 정점을 방문하는 것이 주요한 문제, 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우
- DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.
경로의 특징을 저장해둬야 하는 문제
- 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
최단거리 구해야 하는 문제(미로 찾기 등) 최단거리를 구해야 할 경우, BFS가 유리합니다.
-
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다. -
bfs를 사용할 때, 특징점(ex, 방법의 수, 경로의 수)도 같이 저장할 때는 visit의 원소를 2개 사용한다. (ex, [-1,0])
@flip_404