[백준, C++] 5972 - 택배 배송

https://www.acmicpc.net/problem/5972

5972번: 택배 배송

 

문제 분석

1번 정점에서 N번 정점으로 이동해야 한다. 이동할 때는 정점과 정점 사이를 잇는 간선을 타고 이동하는데, 이 간선에는 음수가 아닌 가중치가 부여되며 간선을 통과할 때 가중치만큼의 비용을 지불한다. 1번 정점에서 N번 정점으로 이동하기 위해 드는 최소한의 비용을 찾는 것이 문제이다.

 

그래프의 간선들이 음이 아닌 가중치를 가질 때, 최소 비용의 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 사용할 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9

using namespace std;

int n, m;
int a, b, c;
vector<pair<int, int>> vec[50001];
priority_queue<pair<int, int>> pq;
int dist[50001];

void getInput();
void solve();
void printResult();

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();
}

void getInput() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        vec[a].push_back({c, b});
        vec[b].push_back({c, a});
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;
    pq.push({-dist[1], 1});

    while (!pq.empty()) {
        pair<int, int> p = pq.top();
        pq.pop();
        int cur = p.second;
        int curDist = -p.first;

        for (int i = 0; i < vec[cur].size(); i++) {
            int nxt = vec[cur][i].second;
            int nxtDist = vec[cur][i].first;

            if (dist[nxt] > curDist + nxtDist) {
                dist[nxt] = curDist + nxtDist;
                pq.push({-dist[nxt], nxt});
            }
        }
    }
}

void printResult() {
    cout << dist[n] << "\n";
}

 

코드 설명

우선순위 큐를 활용해 다익스트라 알고리즘을 구현했다.

 

벡터(vector<pair<int, int>> vec[50001];)에는 해당 정점에서 다른 정점으로 연결된 간선 정보를 담는다. vec[i]에는 i번 정점과 다른 정점을 연결한 간선 정보를 pair<int, int> 형태로 담는다. first에는 간선의 가중치를, second에는 간선을 통해 갈 수 있는 목적지 정점의 번호를 담는다.

 

다익스트라 알고리즘은 DP를 활용한 방식이라고 할 수 있는데, DP 문제를 풀 때 메모이제이션을 위한 배열을 따로 사용하는 것처럼 여기서는 dist 배열(int dist[50001];)을 사용했다. dist 배열은 처음에는 무한대(INF)로 초기화한다. 그리고 이 dist 배열을 최소값들로 갱신해주도록 할 것이다.

 

다익스트라 알고리즘을 더욱 효율적으로 돌리기 위해서 우선순위 큐(priority_queue<pair<int, int>> pq;)를 사용한다. 우선순위 큐에 담는 자료는 pair<int, int>인데, 먼저 second에는 정점의 번호를 담는다. 그리고 first에는 second에서 나타내는 정점까지 가는 데 드는 비용(dist[i])에 음수를 붙여 담는다. 음수로 만드는 이유는, priority_queue가 기본적으로 내림차순이기 때문에 음수로 만들어 dist[i]가 가장 작은 값이 top에 오게 하기 위함이다.

 

우선순위 큐가 빌 때까지 무한루프를 돌며, 우선순위 큐에서 pair<int, int>를 꺼내어 해당 정점에서 연결된 모든 간선을 체크한다. 그리고 그 간선을 활용해 다른 정점으로 이동할 때 드는 비용이 dist[다른 정점]보다 작거나 같다면 갱신하도록 하였다.

 

오랜만에 다익스트라를 풀어서 머리가 잠깐 굳었다. 잊지 말고 자주자주 해야한다 역시 . . .