[BOJ] #1916 최소비용 구하기

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

---

다익스트라 알고리즘을 활용하는 기초중의 기초 문제다. 문제에서 요구하는대로 입력을 받아 다익스트라 알고리즘을 통해 도시간의 최소비용을 구해서 출력하기만 하면 된다.

필자는 다익스트라 알고리즘 구현에 배열 자료구조 대신 우선순위큐를 활용하여 구현하였다. 다익스트라를 구현할때에는 배열을 사용하는 것보다 우선순위큐를 사용하는것이 훨씬 좋다. 정점의 개수를 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;
}

첫번째엔 테스트용 코드를 잘못 제출해서 틀렸고, 두번째는 INF로 초기화하는 과정에서 범위를 잘못 입력해 틀렸다...