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

최단경로 (Gold 5)

문제

전체 문제 보기

1753번: 최단경로

접근법

간선에 가중치가 없는 그래프에서 최단거리는 BFS로 풀 수 있습니다. 하지만 간선에 가중치가 있을 경우 BFS로는 최단 경로를 구할 수 없습니다. 이때는 다익스트라(Dijkstra) 알고리즘을 활용해야 합니다. 다익스트라 알고리즘은 양의 가중치를 가진 경로가 주어졌을 때 최단거리를 구할 수 있는 알고리즘입니다. 시간 복잡도를 살펴보면 BFS는 모든 노드와 간선을 방문하기 때문에 \(O(E + N)\)인 반면에 다익스트라는 우선순위 큐에 후보 노드를 넣어 두고, 비용이 가장 작은 노드를 먼저 뽑는 방식으로 동작합니다. 그럼에도 최악의 경우 모든 노드를 방문해야할 수도 있습니다. 때문에 \(O(E + N\mbox{log}N)\) 시간 복잡도를 가집니다. 그래서 간선에 가중치가 없는 경우 BFS로 푸는 것이 효율 적이고 이번 문제처럼 간선에 가중치가 있는 경우 다익스트라 알고리즘을 활용하는 것이 좋습니다.

 

주의할 점은 다익스트라 알고리즘은 반드시 양의 가중치를 가져야합니다. 가중치에 음수가 존재할 경우 벨만 포드 알고리즘을 사용할 수 있습니다. 이번 문제는 양수 가중치를 가진 최단경로 문제이기 때문에 다익스트라로 해결했습니다.

전체 소스 코드

#include <iostream>
#include <array>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;

const int MAX_VTX = 20'001;
const int INF = MAX_VTX * 10;

struct Edge {
    Edge(struct Node* _target, int _weight) : target(_target), weight(_weight) {}
    Node* target;
    int weight;
};
struct Node {
    vector<Edge> adjacent;
    int dist{ INF };
};

// 이동 비용이 작은 노드가 먼저 오도록
struct Compare {
    bool operator()(Node* lhs, Node* rhs)
    {
        return lhs->dist > rhs->dist;
    }
};
int main() {
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);


    int V, E, start; // (1≤V≤20,000, 1≤E≤300,000) 

    array<Node, MAX_VTX> graph;

    cin >> V >> E >> start;

    for (int i = 0; i < E; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].adjacent.emplace_back(&graph[v], w);
    }

    // 다익스트라
    priority_queue<Node*, vector<Node*>, Compare> pq;
    graph[start].dist = 0;

    pq.push(&graph[start]);
    while (!pq.empty())
    {
        Node* cur = pq.top();
        pq.pop();

        for (Edge edge : cur->adjacent)
        {
            if (edge.target->dist > cur->dist + edge.weight)
            {
                edge.target->dist = cur->dist + edge.weight;
                pq.push(edge.target);
            }
        }
    }

    for (int i = 1; i <= V; ++i)
    {
        if (graph[i].dist == INF)
            cout << "INF" << endl;
        else
            cout << graph[i].dist << endl;
    }

    return 0;
}