[백준] 2982번 - 국왕의 방문 (C++)

• 문제 링크
• 참고 블로그

포스팅 목적

조건에 따라 탐색 도중에 가중치를 수정해줘야 하는 특이한 문제다. 문제 자체가 생각하기에 좋기도 하지만, 이 특이한 특성 때문에 고생한 걸 남겨두고자 함이다.

---

코드 한 줄의 중요성

다익스트라 알고리즘의 while문에서 우선순위 큐로부터 원소 하나를 빼내고 나서 아래 코드를 넣어준다. 이 한 줄을 넣어주든 안 넣어주든 알고리즘은 잘 작동한다.

if (dist[node] < cost) continue;

이 코드의 역할은 해당 조건이 만족되면 어차피 relaxation이 일어나지 않기 때문에, 의미 없는 실행을 줄여서 속도를 높이는 것이다.

근데 이 문제에서는 탐색 도중에 가중치가 수정되기 때문에, 이 코드를 안 넣어주게 되면 확인할 필요도 없었던 간선이 최단 경로에 포함될 수 있다.

---

코드

인접 리스트, 인접 행렬을 둘 다 사용해서 메모리를 아주 비효율적으로 사용했다. 이해하기에는 더 쉬울 수도?

#include <iostream>
#include <queue>
#include <vector>
#define INF 1000000
using namespace std;

vector<pair<int, int> > map[1001];

class Info {
public:
    int node, cost;

    bool operator<(const Info &rhs) const {
        return this->cost > rhs.cost;
    }
};
priority_queue<Info> pq;

int main()
{
    ios_base::sync_with_stdio(false);
    int n, m;
    int a, b, k, g;
    cin >> n >> m >> a >> b >> k >> g;
    vector<int> g_path(g+1);
    vector<int> dist(n+1, INF);
    vector<vector<int> > weight(n+1, vector<int> (n+1));
    vector<vector<pair<int, int> > > control(n+1, vector<pair<int, int> > (n+1));

    for (int i = 1; i <= g; ++i) {
        cin >> g_path[i];
    }
    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        map[u].push_back(make_pair(v, w));
        map[v].push_back(make_pair(u, w));
        weight[u][v] = w;
        weight[v][u] = w;
    }

    int time = 0;
    for (int i = 1; i < g; ++i) {
        int u = g_path[i], v = g_path[i + 1];
        int w = weight[u][v];
        control[u][v] = make_pair(time, time + w);
        control[v][u] = control[u][v];
        time += w;
    }

    dist[a] = k;
    pq.push({a, k});
    while (!pq.empty()) {
        int node = pq.top().node;
        int cost = pq.top().cost;
        pq.pop();
        if (dist[node] < cost) continue; <--------------- 문제의 한 줄
        
        for (int i = 0; i < map[node].size(); ++i) {
            int nextNode = map[node][i].first;
            int nextCost = map[node][i].second;
            auto C = control[node][nextNode];
            if (C.first <= cost && cost <= C.second) {
                nextCost += C.second - cost;
            }
            if (dist[nextNode] > dist[node] + nextCost) {
                dist[nextNode] = dist[node] + nextCost;
                pq.push({nextNode, dist[nextNode]});
            }
        }
    }
    cout << dist[b] - k << endl;

    return 0;
}