[백준] 16118. 달빛 여우 - C++

[Gold I]

 

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

16118번: 달빛 여우

 

풀이 1

몇 번째 step인지를 계산하며, 늑대의 경로를 다익스트라로 잘 계산하면 되겠다 싶었지만,

어느 한 그루터기에 조금 늦게 도착하는 경로가 있더라도, 다른 그루터기에 더 빨리 도착할 수 있는 경로가 될 수 있는데, 그것을 무시하므로 WA.

(예제에서, 아래와 같이 계산하면, 늑대 입장에서 2로 가는 거리는 처음에 1이 된다.

그러나, 4로 가는 경로는 1-2-4 (9)보다 1-3-2-4 (7)가 더 빠른데, 1-3-2 경로를 다익스트라 과정에서 무시하므로 실패.)

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#define init cin.tie(0)->ios_base::sync_with_stdio(0);
#define INF 1e9
using namespace std;
typedef pair<int, int> pint;

vector<pint> edges[4009];
priority_queue<pint, vector<pint>, greater<pint> > pq;
int dist[4009];    // for fox
pint dist2[4009];  // for wolf

int main() {
    init;
    int N, M;
    cin >> N >> M;

    // input edges
    int a, b, d;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> d;
        edges[a].push_back({d, b});
    }

    // dijkstra (fox)
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;
    pq.push({0, 1});

    while (pq.size()) {
        auto [curd, cur] = pq.top();
        pq.pop();
        if (dist[cur] < curd) continue;
        for (int i = 0; i < edges[cur].size(); i++) {
            auto [nxtd, nxt] = edges[cur][i];
            if (dist[nxt] > curd + nxtd) {
                dist[nxt] = curd + nxtd;
                pq.push({dist[nxt], nxt});
            }
        }
    }

    // dijkstra (wolf)
    // dist -> pair<int, int> : first) distance / second) step
    // if step is odd, add half of next dist / if step is even, add twice of next dist.
    for (int i = 1; i < N + 2; i++) {
        dist2[i] = {INF, 0};
    }
    dist2[1] = {0, 0};
    pq.push({0, 1});

    while (pq.size()) {
        int curd = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if (dist2[cur].first < curd) continue;
        for (int i = 0; i < edges[cur].size(); i++) {
            int nxtd = edges[cur][i].first;
            int nxt = edges[cur][i].second;
            if (dist2[cur].second % 2 == 0) {
                nxtd /= 2;
            } else {
                nxtd *= 2;
            }
            if (dist2[nxt].first > curd + nxtd) {
                dist2[nxt] = {curd + nxtd, dist2[cur].second + 1};
                pq.push({dist2[nxt].first, nxt});
            }
        }
    }
}

 

풀이 2

우선, 양방향 간선 그래프이므로 (늑대의 경우, 돌아가는 것이 더 나은 결과를 가져올 수 있음)

edge에 양방향 간선을 추가해 줌.

 

int dist2[4009][2]; // for wolf

또한, 위와 같이 짝수 번째 step에 도달하는 최소 dist와 홀수 번째 step에 도달하는 최소 dist를 따로 저장.

(각자 짝수 번째와 홀수 번째 step에 도달하는 것은 최소 dist로 고정하고, 더 높은 dist가 갱신되려 할 때 무시해도 되는 이유가 - 각각 다음 그루터기로 나아갈 때, 1/2을 할 지, *2를 할 지가 고정되어 있기 때문에, 이렇게 저장해도 무방함.)

 

또한, 아래와 같이 pair<int, pair<int, int>> 를 이용한 Priority Queue로, 몇 번째 step으로 queue에 push되었는 지 확인하여, *2를 할 지, 1/2를 할 지, 그리고 어느 index에 dist를 갱신할 지 나눈다.

typedef pair<int, pair<int, int>> ppint;

priority_queue<ppint, vector<ppint>, greater<ppint>> pq2;

 

마지막으로, 거리가 정수형이기 때문에, /2 를 할 때 부동소수점수 타입으로 바꿔주지 않는 이상, 그대로 제출하면 예제는 맞지만 WA가 나온다. 아래와 같이 간선을 초기화할 때 거리를 두 배로 계산하는 것을 추천.

edges[a].push_back({d * 2, b});
edges[b].push_back({d * 2, a});

 

AC.

 

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#define init cin.tie(0)->ios_base::sync_with_stdio(0);
#define INF 1e9
using namespace std;
typedef pair<int, int> pint;
typedef pair<int, pair<int, int>> ppint;

vector<pint> edges[4009];
priority_queue<pint, vector<pint>, greater<pint>> pq;
priority_queue<ppint, vector<ppint>, greater<ppint>> pq2;
int dist[4009];      // for fox
int dist2[4009][2];  // for wolf

int main() {
    init;
    int N, M;
    cin >> N >> M;

    // input edges
    int a, b, d;
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> d;
        edges[a].push_back({d * 2, b});
        edges[b].push_back({d * 2, a});
    }

    // dijkstra (fox)
    fill(dist, dist + N + 1, INF);
    dist[1] = 0;
    pq.push({0, 1});

    while (pq.size()) {
        auto [curd, cur] = pq.top();
        pq.pop();
        if (dist[cur] < curd) continue;
        for (int i = 0; i < edges[cur].size(); i++) {
            auto [nxtd, nxt] = edges[cur][i];
            if (dist[nxt] > curd + nxtd) {
                dist[nxt] = curd + nxtd;
                pq.push({dist[nxt], nxt});
            }
        }
    }

    // dijkstra (wolf)
    // dist2[i][0] -> even step's dist (next step 1/2) / dist2[i][1] -> odd step's dist (next step *2)
    for (int i = 1; i < N + 2; i++) {
        dist2[i][0] = INF;
        dist2[i][1] = INF;
    }
    dist2[1][0] = 0;

    pq2.push({0, {1, 0}});
    while (pq2.size()) {
        int curd = pq2.top().first;
        int cur = pq2.top().second.first;
        int step = pq2.top().second.second;
        pq2.pop();
        if (step % 2 == 0) {
            if (dist2[cur][0] < curd) continue;
        } else {
            if (dist2[cur][1] < curd) continue;
        }
        for (int i = 0; i < edges[cur].size(); i++) {
            int nxtd = edges[cur][i].first;
            int nxt = edges[cur][i].second;
            if (step % 2 == 0) {
                nxtd /= 2;
                if (dist2[nxt][1] > curd + nxtd) {
                    dist2[nxt][1] = curd + nxtd;
                    pq2.push({dist2[nxt][1], {nxt, step + 1}});
                }
            } else {
                nxtd *= 2;
                if (dist2[nxt][0] > curd + nxtd) {
                    dist2[nxt][0] = curd + nxtd;
                    pq2.push({dist2[nxt][0], {nxt, step + 1}});
                }
            }
        }
    }

    int result = 0;
    for (int i = 1; i < N + 1; i++) {
        if (dist[i] < min(dist2[i][0], dist2[i][1])) result++;
    }
    cout << result;
}