그래프 탐색 알고리즘 비교
| 자료구조 | 큐 사용 | 스택(또는 재귀 호출) 사용 |
| 탐색 방식 | 한 층씩 가로로 확장하며 탐색 | 한 경로를 끝까지 깊게 탐색 후 되돌아옴 |
| 장점 | - 최단 경로 보장- 깊이가 무한히 깊어도 해를 찾을 수 있음 - 얕은 깊이의 해 탐색에 유리 |
- 구현이 간단함 - 메모리 사용량 적음 - 모든 해 탐색(백트래킹 등)에 유리 |
| 단점 | - 큐 사용으로 메모리 소모 큼 | - 불필요하게 깊게 탐색할 수 있음 - 최단 경로 보장하지 않음 |
| 시간복잡도 (인접 리스트) | O(V + E) | O(V + E) |
| 시간복잡도 (인접 행렬) | O(V²) | O(V²) |
BFS (너비 우선 탐색)
BFS는 큐를 이용하여 현재 정점에서 갈 수 있는 인접 정점을 모두 큐에 넣고, 이를 차례대로 탐색하는 방식이다.
즉, 깊게 들어가기보다 가로 방향으로 한 층씩 탐색한다고 이해하면 된다.
장점
- 최단 경로를 보장한다. (특히 가중치가 없는 그래프)
- 해가 존재한다면 깊이가 무한히 깊어도 반드시 찾을 수 있다.
- 노드 수가 적고, 답이 얕은 깊이에 있을 때 유리하다.
단점
- 큐에 탐색 대상을 저장해야 하므로 DFS보다 더 많은 메모리 공간을 사용한다.
시간 복잡도
- 모든 정점(V)과 간선(E)을 한 번씩 탐색한다.
- 표현 방식에 따라 다음과 같이 달라진다.
| 인접 리스트 | O(V + E) | 정점은 최대 한 번, 간선도 최대 한 번 탐색 |
| 인접 행렬 | O(V²) | 각 정점마다 모든 정점과의 연결 여부 검사 |
DFS (깊이 우선 탐색)
DFS는 스택을 이용하여(혹은 재귀 호출) 현재 정점에서 갈 수 있는 경로를 따라 끝까지 들어간 뒤, 더 이상 갈 곳이 없으면 되돌아오는 방식이다.
즉, 한 경로를 끝까지 파고드는 탐색이라고 볼 수 있다.
장점
- 구현이 간단하다. (재귀 호출로도 쉽게 가능)
- BFS보다 메모리 사용량이 적다.
- 모든 해를 탐색해야 하는 경우(예: 경로 탐색, 백트래킹 문제)에 유리하다.
단점
- 해가 깊은 곳에 없으면 불필요하게 깊이 탐색할 수 있다.
- 최단 경로를 보장하지 않는다.
시간 복잡도
- BFS와 동일하게 모든 정점(V)과 간선(E)을 한 번씩 탐색한다.
- 표현 방식에 따라 달라진다.
| 인접 리스트 | O(V + E) | 정점은 최대 한 번, 간선도 최대 한 번 탐색 |
| 인접 행렬 | O(V²) | 각 정점마다 모든 정점과의 연결 여부 검사 |
'CS > 알고리즘' 카테고리의 다른 글
| 길 찾기 알고리즘 비교 (0) | 2025.10.02 |
|---|