최단경로(C++) 백준 1753

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

풀이방법

본 문제는, 다익스트라 알고리즘으로 풀면 된다. 다익스트라란, 그래프에서 '최소 비용'을 구해야 하는 경우 유용하게 사용된다. 시작노드 ~ 도착노드가 주어진 경우 최소 비용의 경로를 구할 때 자주 사용되므로 알고리즘의 방식을 잘 이해하여 자유롭게 사용 할 수 있어야 된다.

먼저, 본 문제에서는 가중치의 입력이 10이하의 자연수로 이루어져 있으므로 음의 경우는 생각을 안해줘도 된다. 우선, 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드는 자신에게 가는것은 당연히 가중치가 0이므로 바로 가중치를 0으로 지정해준다. 그 후, 시작 노드와 연결된 정점들의 가중치들의 값들 중 가장 낮은 가중치를 가진 것 부터 비교 해주면 된다.

이 때, 가장 낮은 가중치를 확인해주기 위해서 그래프의 모든 원소를 반복하며 확인해주는 것 보다는 STL에서 제공해주는 priority queue를 이용하면 더 쉽게 풀 수 있다.
priority queue를 priority_queue<pair<int,int>> pq;로 선언하고 first를 가중치로
설정하고 진행하면 되는데, 이 때 우선순위 큐는 값의 큰 순서대로 정렬을 하므로 부호를 반대로 넣어주고 pq.top()으로 받아올때 또 다시 부호를 반대로 해 원래값으로 바꿔주면 최소힙으로 구현 할 수 있다.

또한, 정점이 가진 현재 가중치가 부모 노드의 가중치 + 현재 연결된 가중치 보다 크다면 정점의 가중치를 부모 노드의 가중치 + 현재 연결된 가중치로 바꿔준다.

이렇게 진행하면, 방문한 정점들과 연결되어 있는 정점들 중에 가중치가 가장 적게 드는 정점을 선택 해주는 코드가 완성된다.

코드

#include<iostream>
#include<queue>

using namespace std;
#define INF 987654321
#define MAX 20000 + 1
int start, V, E;

int dist[MAX];
vector<pair<int,int>> graph[MAX]; //graph[idx] (first,second) idx = 해당 정점 first = 연결된 값 second = 가중치


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

void DijkstraSolve()
{
    //first 가중치 second 정점
    priority_queue<pair<int,int>> pq;
    pq.push({0,start});
    dist[start] = 0;

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

        for(int i = 0; i < graph[curidx].size(); ++i)
        {
            int next = graph[curidx][i].first; //연결된 인덱스
            int nCost = graph[curidx][i].second;  //연결된 인덱스까지의 가중치
            if(dist[next] > cost + nCost)
            {
                dist[next] = cost + nCost;
                pq.push({-dist[next],next});
            }
        }
    }

    for(int i = 1; i <= V; ++i)
    {
        if(dist[i] == INF)
        {
            cout << "INF" << '\n';
        }
        else
        {
            cout << dist[i] << '\n';
        }   
    }
}


int main()
{
    cin >> V >> E;

    cin >> start;

    int from, to, w;

    while(E--)
    {
        cin >> from >> to >> w;
        graph[from].push_back({to,w});
    }

    for(int i = 1; i <= V; ++i)
    {
        dist[i] = INF;
    }

    DijkstraSolve();

    return 0;
}