[BOJ/C++] 최단경로(1753번)

1. 개요

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

1753번: 최단경로

1-1. 설명

방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성한다. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 

1-2. 제한 사항

 - 첫 줄에 정점 개수 V, 간선 개수 E가 주어지며, V는 1 이상 20,000이하이고 E는 1 이상 300,000 이하

 - 모든 정점은 1부터 V까지 번호가 매겨져 있다고 가정

 - 둘째 줄에는 시작 정점의 번호 K가 주어지며, K는 1 이상 V 이하

 - 셋째 줄부터 E개 줄에 걸쳐 각 간선을 나타내는 세 개의 정수가 주어짐

 - (u, v, w) -> u에서 v로 가는 가중치가 w인 간선, u와 v는 서로 다르며 w는 10 이하 자연수

---

2. 구현

2-1. 풀이

다익스트라 알고리즘의 기본 문제이다. 초반에는 vector로 단순하게 구현하다가, 컴파일 에러가 자꾸 떠서 https://yabmoons.tistory.com/364에서 우선 순위 큐 구현에 대해 공부한 후, 새로 구현하였다. 다음에는 코드를 참고하지 않고 혼자서 짜봐야겠다. 

2-2. 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

constexpr size_t MAX_NUM = 20001;
constexpr size_t INF = 999999999;
vector<pair<int, int>> graph[MAX_NUM];
int dist[MAX_NUM];

void dijkstra(int V, int start);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int V, E, start;
    cin >> V >> E >> start;

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

    fill_n(dist, V+1, INF);
    dijkstra(V, start);

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

    }
    return 0;
}

void dijkstra(int V, int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> priQue;
    // 값이 작을 수록 우선순위를 갖는 최소힙으로 사용
    priQue.push(make_pair(0, start));
    dist[start] = 0;

    while (!priQue.empty()) {
        int cost = priQue.top().first; // 현재 노드까지 비용
        int curNode = priQue.top().second; // 현재 노드
        priQue.pop();

        for (int i = 0; i < graph[curNode].size(); i++) { // 현재 노드에서 다음 노드들 비용 계산하기 위한 for 문 
            int next = graph[curNode][i].first;
            int nextCost = graph[curNode][i].second;
            
            if (dist[next] > cost + nextCost) { // 갱신
                dist[next] = cost + nextCost;
                priQue.push(make_pair(dist[next], next));
            }
        }
    }
}