[C++] 백준 1753 최단경로 [Gold4]

문제

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

풀이

시작점에서 다른 모든 정점으로의 최단 경로는 다익스트라 알고리즘으로 구할 수 있다. BFS 와 비슷하며 알고리즘 개념은 다음과 같다.

다익스트라 알고리즘

1. 현재 노드와 연결된 노드를 찾으면서 누적 거리 값을 계산한다.

2. 연결된 노드가 가지고 있는 거리 값이 현재 누적된 거리값 보다 크다면, 현재 누적된 거리가 최단 경로 이므로 업데이트 한다. ( 기본적으로, 모든 노드는 무한대 값으로 거리 값이 초기화 되어있다.)

3. 다음으로, 현재 알고 있는 누적 거리 중 가장 최소인 정점을 선택해서 뻗어나간다.

4. 3번 과정에서 현재 누적 거리가 최소인 정점을 선택해서 뻗어 나가기 때문에, 한번 업데이트가 된 노드가 다시 방문될 수 있고 2번 과정에 의해 최소값으로 업데이트 된다.

5. 3번 과정에서 우선순위 큐를 사용한다면, 최소값을 찾는 과정을 O(logN)에 해결할 수 있다.

 

리뷰

INT_MAX 값을 define 하지 않으면 백준에서 채점을 돌릴 때 컴파일 에러가 난다.

vscode 상에서도 c++17이고 백준에서도 c++17인데 컴파일러 차이 때문인지 ..

찾아보니 #include <climits> 안에 INT_MAX 가 정의되어 있으니 포함 시키면 해결된다.

#include <iostream>
#include <queue>
#include <algorithm>

#define INT_MAX 2147000000
using namespace std; 

struct Edge{
    int vex;
    int dis;
    Edge (int a, int b)
    {
        vex = a;
        dis = b;
    }
    bool operator<(const Edge &a) const {
        return dis > a.dis; 
    }
};

int main()
{
    // freopen("1753.txt", "r", stdin);

    int i, n, st, m, a, b, c, cnt=0, res=0;
    cin >> n >> m;
    cin >> st;

    vector<vector<pair<int, int> >> graph(n+1);
    priority_queue<Edge> pq;
    vector<int> dist(n+1, INT_MAX);

    for (i=1; i<=m; i++){
        cin>>a>>b>>c;
        graph[a].push_back({b, c});
    }

    
    pq.push(Edge(st, 0));
    dist[st] = 0;

    while (!pq.empty()) {
        int now = pq.top().vex;
        int cost = pq.top().dis;
        pq.pop(); 

        if (cost > dist[now]) continue;

        for (int i=0; i<graph[now].size(); i++){
            int next = graph[now][i].first;
            int nextDist = cost + graph[now][i].second;

            if (dist[next] > nextDist) {
                dist[next] = nextDist;
                pq.push(Edge(next, nextDist));
            }
        }
    }   

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