문제 푼 날짜 : 2021-07-04

문제

문제 링크 : https://www.acmicpc.net/problem/1753

접근 및 풀이

최단경로를 구하는 기본 중의 기본 알고리즘인 다익스트라(Dijkstra) 알고리즘을 이용하는 문제였다.
다익스트라 알고리즘은 가중 그래프(Weighted Graph)에서 하나의 시작 노드(출발점)에서 출발점을 제외한 모든 다른 노드까지의 최단거리를 구하는 알고리즘이다.
우선순위 큐를 이용해 다음으로 탐색할 노드를 저장해주며, 시작 노드에서 다른 노드까지의 거리를 계산하는 배열을 이용하여 최단거리를 갱신해준다.
다익스트라 알고리즘에 관한 시각적 설명이 잘 되어있는 [사이트]를 참고하여 문제를 해결하였다.

코드

// 백준 1753번 : 최단경로
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 987654321

int dist[20001];
vector<pair<int, int>> road[200001];

void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));

    while(!pq.empty()) {
        int distance = -pq.top().first;
        int current = pq.top().second;
        pq.pop();

        if (dist[current] < distance) {
            continue;
        }
        for (int i = 0; i < road[current].size(); i++) {
            int next = road[current][i].first;
            int nextDistance = distance + road[current][i].second;

            if (nextDistance < dist[next]) {
                dist[next] = nextDistance;
                pq.push(make_pair(-nextDistance, next));
            }
        }
    }
}

int main() {
    int V, E, K;

    cin >> V >> E >> K;

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

    while(E--) {
        int u, v, w;
        cin >> u >> v >> w;
        road[u].push_back(make_pair(v, w));
    }

    dijkstra(K);

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

피드백

코딩 테스트를 공부하면서 다익스트라를 이용하는 문제가 심심치 않게 등장하는 것을 알게되었다. 알고리즘 수업때 다익스트라에 대해 배우긴 했지만 개념이 머릿속에서 희미해져 있었기 때문에 관련문제를 풀어보기로 하였다.