[BaekJoon 1753번] 최단경로(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를 출력하면 된다.

 

 

[입출력 예]

 

 

입력	출력
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6	0 2 3 7 INF

 

 

[문제 풀이]

 

 

다익스트라 알고리즘 문제이다.

다익스트라 이해를 위해 동빈나님의 알고리즘 강의 중 다익스트라를 듣고 난 후

공부하여 내 입맛에 알맞게 코드를 구현하였다.

 

다익스트라에 대한 자세한 내용은 영상 참고.

 

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9 // 최댓값

int V; // 정점의 개수
int E; // 간선의 개수
int K; // 시작 정점
vector<int> cost; // 최소 비용 저장
vector<pair<int, int>> graph[20001]; // 연결 정점, 가중치

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 최소힙,  {가중치, 정점} 적은 가중치가 맨 앞에 오도록 함

void dijkstra(int cur) {
    pq.push({0, cur});
    cost[cur] = 0;
    while(!pq.empty()) {
        int cur_node = pq.top().second; // 현재 정점
        int cur_cost = pq.top().first; // 현재 가중치
        pq.pop();
        for(pair<int, int> element : graph[cur_node]) {
            int next_node = element.first;
            int next_distance = element.second + cur_cost;
            if(next_distance < cost[next_node]) {
                cost[next_node] = next_distance;
                pq.push({next_distance, next_node});
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> V >> E; // 정점의 개수, 간선의 개수
    cin >> K; // 시작 정점
    cost.resize(V + 1);
    for(int i = 0; i < E; ++i) {
        int start, end, cost;
        cin >> start >> end >> cost;
        graph[start].emplace_back(make_pair(end, cost));
    }

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

    dijkstra(K); // 시작 정점

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