그래프 탐색 알고리즘: DFS/BFS
어떠한 한 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 정점을 모두 찾는 알고리즘
- 그래프: 정점과 간선으로 이루어진 자료구조의 일종
DFS(깊이 우선 탐색: Depth-First Search)
그래프에서 최대한 깊이 내려간 뒤, 더 이상 내려갈 곳이 없을 경우 옆으로 이동한다.
💡 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 예) 미로를 탐색할 때, 한 방향으로 쭉 가다가 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행하는 방법
💡 특징
1. 스택 또는 재귀 함수로 구현
2. 모든 노드를 방문하고자 하는 경우
3. 검색 속도가 BFS에 비해서 느림
BFS(너비 우선 탐색: Breadth-First Search)
그래프에서 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
💡 시작 정점으로부터 인접한 노드부터 먼저 탐색하는 방법
💡 특징:
1. 큐를 이용해서 구현
2. 미로 탐색과 같이 최단 경로를 찾고 싶을 때 사용
DFS/BFS 차이점
| DFS | BFS |
|---|---|
| 현재 정점에서 갈 수 있는 점들까지 깊이 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
| 모든 정점 방문이 필요하다면 추천 | 최단거리를 구해야 한다면 추천 |
시간 복잡도
| 인접 행렬 | 인접 리스트 |
|---|---|
| O(V^2) | O(V+E) |
💡 두 알고리즘의 시간 복잡도는 같다. 다만 인접 행렬로 구현하느냐 인접 리스트로 구현하느냐에 따라 복잡도가 달라진다.
💡 메모리 효율: 인접 행렬(모든 관계를 저장하므로) < 인접 리스트
💡 조회 속도: 인접 행렬 (graph[0][0]와 같이 바로 접근 가능) > 인접 리스트 (노드에 대한 인접 리스트 모두 조회)
DFS/BFS 문제 유형
- 그래프의 모든 정점을 방문하는 문제
단순히 모든 정점을 방문하는 것이 중요한 경우 두 방법 중 어느 것을 사용해도 상관없다. 편한 것을 사용하면 된다.
- 경로의 특징을 저장해두어야 하는 문제
예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구해야 하는데 경로에 같은 숫자가 있으면 안 되는 문제 등, 각 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다.
- 최단거리를 구하는 문제
미로 찾기 등 최단거리를 구해야할 경우 BFS가 유리하다. 왜냐하면 DFS로 탐색을 할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있어서 모든 정점을 방문할 가능성이 있다. 하지만, BFS의 경우 현재 노드에서부터 가까운 곳부터 찾기 때문에 먼저 찾아지는 해답이 곧 최단거리이다.
💡 예시) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고 Sam과 Eddie 사이에 존재하는 경로를 찾을 경우
깊이 우선 탐색: 모든 친구 관계를 살펴봐야 할 수도
너비 우선 탐색: Sam과 가까운 관계부터 탐색
💡 추가 설명: 시작점에서 모든 점까지의 최단거리는 달리 말하면 필요한 최소 간선 개수이다. BFS는 시작점에서 가까운 점부터 탐색을 하기 때문에, 간선의 가중치가 모두 동일하다면 최단거리를 O(V+E)에 구할 수 있다.
