[알고리즘] 너비 우선 탐색(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