문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
풀이
방향 그래프에서 시작점 하나가 주어지고, 모든 정점까지의 최단 거리를 구해야 하므로 전형적인 다익스트라 문제다. 간선 가중치가 모두 양수이기 때문에 우선순위 큐를 이용한 거리 확정 방식이 그대로 통한다.
코드에서는 시작 정점 K의 거리를 0으로 두고 우선순위 큐에 넣는다. 이후 가장 비용이 작은 정점을 꺼내고, 그 값이 dist 배열에 기록된 값보다 크면 오래된 정보이므로 건너뛴다. 아니라면 인접 정점들에 대해 더 짧은 경로가 나오는지 확인하며 거리 완화를 수행한다.
또한 도달할 수 없는 정점은 끝까지 INF로 남기 때문에, 마지막 출력에서 그대로 구분할 수 있다. 핵심은 방문 배열 없이도 dist 기준으로 오래된 큐 원소를 버리면 다익스트라가 깔끔하게 구현된다는 점이다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 987654321;
void solve() {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<pair<int, int>> vec[20001];
int dist[20001];
int V, E, K, u, v, w;
cin >> V >> E >> K;
for (int i = 0; i < E; i++) {
cin >> u >> v >> w;
vec[u].push_back({v, w});
}
fill_n(dist, 20001, INF);
dist[K] = 0;
pq.push({0, K});
while(!pq.empty()) {
int cost = pq.top().first;
int cur = pq.top().second;
pq.pop();
if (cost > dist[cur])
continue;
for (int i = 0; i < vec[cur].size(); i++) {
int next = vec[cur][i].first;
int nextCost = cost + vec[cur][i].second;
if (nextCost < dist[next]) {
dist[next] = nextCost;
pq.push({nextCost, next});
}
}
}
for (int i = 1; i <= V; i++) {
if (dist[i] == INF)
cout << "INF" << '\n';
else
cout << dist[i] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
최단경로 문제는 다익스트라의 기본 흐름을 가장 잘 보여준다. 큐에서 꺼낸 값이 최신 거리인지 확인하는 습관만 잡아도 구현이 한결 안정적이다.
