[알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)

0. 그래프 탐색 문제란?

 

- 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)를 타고 이동할 수 있는 정점(Vertex, V)를 모두 찾는 문제

- 문제 해결법: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다.

 

---

1. 너비 우선 탐색(BFS)이란?

- BFS (Breadth - First Search)

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것

- 두 노드 사이의 최단 경로 / 임의의 경로를 찾을 때 사용

 

---

2. 너비 우선 탐색의 특징

- 직관적 X : 시작 노드에서 출발하여 거리에 따라 단계별로 탐색

- 재귀적으로 동작 X

- 그래프 탐색 시,  어떤 노드를 방문했었는지 여부를 반드시 검사! (검사하지 않으면, 무한루프의 가능성)

- 큐(Queue) 사용 : 방문한 노드들을 차례로 저장한 후, 꺼내기 위한 자료구조

- 요구사항: 선입선출(FIFO) 원칙으로 탐색 (deque 사용)

- 그래프의 간선의 가중치가 모두 동일할 때, BFS는 효과적!

 

* 시간 복잡도

- 인접 리스트로 표현된 그래프: O(N+E)

- 인접 행렬로 표현된 그래프 : O(N^2)

- 희소 그래프의 경우, 인접 리스트를 사용하는 것이 유리

 

---

3. 너비 우선 탐색의 과정

- 같은 깊이에 있는 모든 노드를 방문하고, 더 깊은 노드로 계속 방문

- 더 이상 방문할 곳이 없으면, 탐색을 마침.

 

---

4. 깊이 우선 탐색(DFS)이란?

- DFS(Depth - First Search)

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

- ex. 미로 : 한 방향으로 갈 수 있을 때까지 계속 감.

                : 더 이상 갈 수 없으면, 지금 위치에서 가장 가까운 갈림길로 돌아감.

                : 돌아간 갈림길의 위치에서 다른 방향으로 다시 탐색을 진행.

- 넓게(Wide) 탐색 하기 전에 깊게(Deep) 탐색 하는 것

- 모든 노드를 방문하고자 하는 경우 사용

---

5. 깊이 우선 탐색의 특징

- 자기 자신을 호출하는 순환 알고리즘의 형태

- 트리 순회(전위, 중위, 후위)는 모두 DFS의 한 종류

- 그래프 탐색 시,  어떤 노드를 방문했었는지 여부를 반드시 검사! (검사하지 않으면, 무한루프의 가능성)

- 구현 방법: 1) 순환 호출 이용 2) 명시적인 스택 사용

 

* 시간 복잡도

- DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회

- 인접 리스트로 표현된 그래프: O(N+E) ~ 메모리 효율 good
- 인접 행렬로 표현된 그래프: O(N^2) ~ 조회 속도 fast

- 희소 그래프의 경우, 인접 리스트를 사용하는 것이 유리

 

---

6. 깊이 우선 탐색의 과정

 

---

7. 참고

- https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

- https://jin1ib.tistory.com/entry/BFS-DFS-1

- https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html