[BOJ] #1916 최소비용 구하기
https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
다익스트라 알고리즘을 활용하는 기초중의 기초 문제다. 문제에서 요구하는대로 입력을 받아 다익스트라 알고리즘을 통해 도시간의 최소비용을 구해서 출력하기만 하면 된다.
필자는 다익스트라 알고리즘 구현에 배열 자료구조 대신 우선순위큐를 활용하여 구현하였다. 다익스트라를 구현할때에는 배열을 사용하는 것보다 우선순위큐를 사용하는것이 훨씬 좋다. 정점의 개수를 V, 간선의 개수를 E라고 했을때, 배열을 이용하는 방법은 O(V^2), 우선선위 큐를 이용하는 방법은 O(E logV)의 시간복잡도를 따른다. 배열을 사용했을때 시간복잡도가 커지는 이유는 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색하고, 현재 노드와 연결된 노드를 일일이 확인하기 때문이라고 한다.
최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 배열을 이용한 다익스트라 알고리즘을 활용해도 괜찮다. 하지만 10,000개를 넘어가는 문제라면 우선순위큐를 활용한 다익스트라를 이용하는게 좋다고 한다.
#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
#define INF 999999999
using namespace std;
vector<pair<int,int>> Graph[MAX];
int cost[MAX];
void dijkstra(int start) {
cost[start] = 0;
priority_queue<pair<int,int>> pq;
pq.push(make_pair(start,0));
while (!pq.empty()) {
int current = pq.top().first;
int dist = -pq.top().second;
pq.pop();
if (cost[current] < dist) continue;
for (int i=0; i<Graph[current].size(); i++) {
int newCurr = Graph[current][i].first;
int newDist = dist + Graph[current][i].second;
if (newDist < cost[newCurr]) {
cost[newCurr] = newDist;
pq.push(make_pair(newCurr, -newDist));
}
}
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int V,E;
cin >> V >> E;
for (int i=1; i<=V; i++) cost[i] = INF;
for (int i=0; i<E; i++) {
int a,b,c;
cin >> a >> b >> c;
Graph[a].push_back(make_pair(b,c));
}
int startingPoint, destination;
cin >> startingPoint >> destination;
dijkstra(startingPoint);
cout << cost[destination] << '\n';
//for (int i=1; i<=V; i++) cout << cost[i] << ' ';
return 0;
}