[BOJ] 최단경로 1753 (C++) - 39일차

문제

1753번: 최단경로

생각

다익스트라 알고리즘을 활용한 문제이다.

 

다익스트라 알고리즘은 시작점을 기준으로 인접한 노드들을 방문하며 시작점에서 해당 노드까지의 최소 거리를 찾는 알고리즘입니다.

인접한 노드들을 방문한 뒤에는 인접한 노드들의 인접한 노드들을 확인하는 방식으로 작동합니다.

한 가지 주의할 점은 인접한 노드들을 방문할 때 비용이 최소인 노드부터 방문하므로 우선순위 큐에 비용을 음수 처리하여 넣어야 한다는 점입니다.

Priority Queue는 기본적으로 값의 크기대로 우선순위를 부여하기 때문에 위와 같이 처리해야합니다.처: https://jaimemin.tistory.com/555 [꾸준함]

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 987654321;

vector<pair<int, int>> graph[20001];
int d[200001];

void dijkstra (int start) { 
    priority_queue<pair<int,int>> pq;
    pq.push({0, start}); //초기 비용과 시작점
    d[start] = 0; //자기 자신한테 가는 비용 0

    while(!pq.empty()) {
        int dist = - pq.top().first; //현재 노드까지의 비용
        							//거리의 부호를 바꾸어 거리가 작은 정점부터 꺼내지게 하였으므로 부호를 바꿔준다
        int now = pq.top().second; // 현재 노드
        pq.pop();
        
        if(d[now] < dist) // 이미 최단경로를 체크한 노드인 경우 패스
            continue;

        for(int i=0; i<graph[now].size(); i++) {
        	int neigbor = graph[now][i].first;
            int cost = dist + graph[now][i].second; // 거쳐서 가는 노드의 비용을 계산
                                                    // 현재노드까지 비용 + 다음 노드 비용
            if(cost < d[neighbor]) // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            {
                d[neighbor] = cost;
                pq.push(make_pair(-cost, neighbor)); //거리의 부호를 바꾸어 거리가 작은 정점부터 꺼내지도록하기 위해
            }
        }
    }
}

int main() {
    int v, e;
    cin >> v >> e;
    int st;
    cin >> st;

    for(int i = 0; i < e; i++) {
        int source, destination, cost;
        cin >> source >> destination >> cost;
        graph[source].push_back({destination, cost});
    }
    for(int i = 0; i <= v; i++) {
        d[i] = INF;
    }

    dijkstra(st);

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