DFS / BFS

1. 깊이 우선 탐색(DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

1. 모든 노들르 방문하고자 하는 경우에 이 방법을 선택
2. DFS가 BFS보다 좀 더 간단함
3. 검색 속도 자체는 BFS에 비해서 느림

2. 너비 우선 탐색(BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택

3. DFS와 BFS 비교

DFS와 BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일

N은 노드, E는 간선일 때

인접 리스트 : O(N + E)
인접 행렬 : O(N^2)

일반적으로 E(간선)의 크기가 N^2에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적이다.

4. DFS와 BFS 활용한 문제 유형/응용

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제
   단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관 없다.
2. 경로의 특징을 저장해둬야 하는 문제
   DFS 사용(BFS는 경로의 특징을 가지지 못한다.)
3. 최단거리 구해야 하는 문제
   미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리
4. 검색 대상 그래프가 매우 큰 경우
   DFS 고려
5. 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS