다익스트라 알고리즘 (백준 1916)

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이방법

전형적인 다익스트라 알고리즘을 사용해 푸는 문제이다. 여기서 조심해야 할 점은 시간초과가 뜰 수 있는데, 이 때, 다익스트라 알고리즘 코드 내부에

if (dist[curIdx] < curCost) continue;

이 구문을 추가 해 줘야 한다. 이 구문은 우선순위큐에 추가되어있던 튜플 원소 {비용,현재 방문한 정점}에서 이전에 계산된 최소 거리 비용과 현재 우선순위 큐에 있는 비용을 비교해주는 구문이다.

만약 dist[curIdx] 즉, 이미 계산된 비용이 curCost 즉, 현재 우선순위큐에있는 비용보다 크다면 for문에 진입하지 않고 바로 우선순위큐의 다음 원소를 확인해주는 방식으로 동작 시간을 크게 줄여 줄 수있다.

즉, 이미 계산 된 방문 한 정점까지의 최소 거리와 현재 우선순위 큐의 같은 인덱스를 가진 원소의 비용을 비교하여 우선순위 큐의 비용이 더 작을때에만 for문에 진입하는 것이다.

코드

#include <iostream>
#include <queue>
#define MAX 1000 + 1
#define INF 987654321

using namespace std;

vector<pair<int, int>> graph[MAX];
int dist[MAX];

int N, M; //도시의 개수 버스의 개수

void Dijkstra(int start, int goal)
{

    priority_queue<pair<int, int>> pq;
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty())
    {
        int curIdx = pq.top().second;
        int curCost = -pq.top().first;
        pq.pop();

        if (dist[curIdx] < curCost)
            continue;

        for (int i = 0; i < graph[curIdx].size(); ++i)
        {
            int Next = graph[curIdx][i].first;
            int Ncost = graph[curIdx][i].second + curCost; //다음 정점까지 가는데 걸린 비용 -> 현재까지 온 비용 + 다음 정점까지의 비용
            if (dist[Next] > Ncost)
            {
                dist[Next] = Ncost;
                pq.push({-Ncost, Next});
            }
        }
    }
}

void Init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    Init();

    int start, goal;

    cin >> N >> M;

    for (int i = 0; i < M; ++i)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
    }

    cin >> start >> goal;

    for (int i = 0; i <= N; ++i)
    {
        dist[i] = INF;
    }

    Dijkstra(start, goal);

    cout << dist[goal] << '\n';

    return 0;
}