코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
최단 경로 문제: 가중 그래프에서 두 정점 사이 최소 비용 경로 찾기
BFS는 비가중 그래프에서만 최단 경로를 보장 → 가중 그래프에서는 다른 알고리즘 필요!
4가지 주요 알고리즘:
| 알고리즘 | 유형 | 음수 가중치 | 시간 |
|---------|------|-----------|------|
| Dijkstra | 단일 출발점 | 불가 | O((V+E)log V) |
| Bellman-Ford | 단일 출발점 | 가능 | O(VE) |
| Floyd-Warshall | 모든 쌍 | 가능 | O(V³) |
| BFS | 단일 출발점 | 비가중만 | O(V+E) |
선택 기준:음수 가중치 없음 → Dijkstra (가장 빠름)
음수 가중치 있음 → Bellman-Ford
모든 쌍 최단 거리 → Floyd-Warshall
비가중 그래프 → BFS (가장 간단)
오늘은 그래프 심화 알고리즘을 배워보겠습니다.
지난 시간에 BFS로 최단 경로를 찾았는데요, 그건 간선 가중치가 모두 같을 때만 맞아요.
만약 도로마다 거리가 다르면 어떻게 해야 할까요?
그림 왼쪽의 결정 트리를 보세요.
먼저 "모든 쌍의 최단 거리가 필요한가"를 판단합니다.
네라면 Floyd-Warshall, 아니라면 다음 질문으로 넘어가요.
"음수 가중치가 있는가"를 확인하는 거죠.
음수가 있으면 Bellman-Ford를 선택해야 합니다.
음수가 없고 가중치가 있으면 Dijkstra가 가장 빠른 선택이에요.
비가중 그래프라면 그냥 BFS면 충분하고요.
오른쪽 비교표를 보시면 네 알고리즘의 시간 복잡도가 정리되어 있어요.
Dijkstra는 힙을 쓰면 O((V+E)logV)로 상당히 빠릅니다.
Bellman-Ford는 O(VE)로 좀 느리지만 음수를 처리할 수 있어요.
Floyd-Warshall은 O(V³)인데 모든 쌍을 한번에 구하니까 그만한 가치가 있죠.
여기서 중요한 건 "왜 Dijkstra는 음수에서 실패하는가"입니다.
Dijkstra는 한번 확정한 거리를 다시 바꾸지 않는 그리디 방식이에요.
음수 간선이 있으면 확정 후에 더 짧은 경로가 발견될 수 있거든요.
이게 바로 Bellman-Ford가 필요한 이유입니다.
Dense 그래프, 즉 간선이 많은 경우에는 Floyd가 유리하고요.
Sparse 그래프에서는 Dijkstra가 압도적으로 빠릅니다.
이 네 가지 알고리즘을 하나씩 자세히 살펴볼게요.