BOJ 16118 달빛여우

백준 16118 링크

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

정말 어렵게 풀었습니다 😣

대략 이 문제를 접한지 2~3주 만에 풀었습니다. 처음엔 금방 풀 수 있을줄 알았는데 그게 아니었습니다. 여러 사람들에게 물어보고 또 질문하고, 다시 한번 물어보고(이해가 안되서 물어봄), 생각해보고. 그러던 끝에, 해답을 알게 되었습니다. 이제와서 생각해보니 크게 어려운건 아닌거같기도 하고 🙄

처음에 접근한 방법

다익스트라 문제인건 알겠는데 어떻게 해결하지?

 

아하, 여우와 늑대가 다익스트라 하는것을 각각 따로 만들어서 해주면 되겠지.

 

그냥 여우 거리 배열(dp_f[]),늑대 거리 배열(dp_w[]) 만들어서 하면 될꺼야.

 

그러면 처음엔 느리다가 나중에 빨라지는 경우를 구할 수 가 없게 됩니다. 🤔

 

어떻게 하지??

문제 풀이

여우는 그냥 다익스트라로 구하면 되니까 더 건들 필요는 없을꺼고 늑대를 조금 더 건들면 될거같은데.

 

늑대 다익스트라를 빠른 경우와 느린 경우로 나눠주고 거리 배열도 빠를 때(dp_wf[])와 느릴 때(dp_ws[])로 나눠봅시다.

 

느리게 움직일때는 dp_ws[] 와 dp_wf[] + (가중치/2)를 비교하고 큐에 다음에 빠르게 움직이도록 psuh

 

빠르게 움직일때는 dp_wf[] 와 dp_ws[] + (가중치*2)를 비교하고 큐에 다음에 느리게 움직이도록 psuh

 

이렇게 하면 빠를때와 느릴때 각각 최소로 움직이는 경우를 구할 수 있습니다.

이렇게 하면 된줄 알았죠?

저도 이렇게 하면 된줄 알고 제출을 했는데 시간제한이라고 알려줍니다. 😨

 

다익스트라에서 시간을 줄이는 방법은 지금 큐에서 꺼낸 노드의 가중치와 dp에 기록된 가중치가 같은지 확인하는 절차를 거치면 시간이 조금 줄어듭니다.

if(cost != dp[now]) continue;

같다면 진행하고 같지 않다면 지금 가중치는 의미가 없을테니 넘어갑시다.

 

다른 사람들한테 알고리즘 설명해주는걸 정말 좋아합니다. 혹시 저의 글이 부족하다고 생각되면 꼭 댓글로 리뷰나 질문부탁드릴게요.

코드

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
typedef struct wolf {
    int record; 
    int node;
    bool fast; //0은 느림 1은 빠름
};
bool operator < (wolf a, wolf b) {
    return a.record < b.record;
}
int n, m;
int dp_f[4003], dp_wf[4003], dp_ws[4003]; 
vector <pair<int, int>> con[4003];
priority_queue <wolf> wolf_q;
priority_queue <pair<int, int>> fox_q;
int min(int a, int b) {
    return a < b ? a : b;
}
int main() {
    //    freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    while (m--) {
        int a, b;
        int c;
        scanf("%d %d %d", &a, &b, &c);
        con[a].push_back({ b,c * 2 }); //이 부분에서 가중치를 2배로 받음
        con[b].push_back({ a,c * 2 }); //이 부분에서도
    }
    for (int i = 1; i <= n; i++) dp_f[i] = dp_ws[i] = dp_wf[i] = 2e9;
    
    //여우 다익스트라
    dp_f[1] = 0;
    fox_q.push({ 0,1 });
    while (!fox_q.empty()) {
        int cost = -1 * fox_q.top().first;
        int now = fox_q.top().second;
        fox_q.pop();
        if (cost != dp_f[now]) continue;
        for (auto i : con[now]) {
            int next = i.first;
            if (dp_f[now] + i.second < dp_f[next]) {
                dp_f[next] = dp_f[now] + i.second;
                fox_q.push({ -1 * dp_f[next], next });
            }
        }
    }
    //여우 다익스트라
    
    //늑대 다익스트라
    wolf_q.push({ 0,1,true });
    dp_ws[1] = 0;
    while (!wolf_q.empty()) {
        int now = wolf_q.top().node;
        int record = -1 * wolf_q.top().record;
        bool fast = wolf_q.top().fast;
        wolf_q.pop();
        if (fast) {
            if (dp_ws[now] != record) continue;
        }
        else {
            if (dp_wf[now] != record) continue;
        }
        for (auto i : con[now]) {
            if (fast) { //늑대가 빠르게갈때는 가중치 반으로 해서 더해줌
                int next = i.first;
                if (dp_ws[now] + (i.second / 2) < dp_wf[next]) {
                    dp_wf[next] = dp_ws[now] + (i.second / 2);
                    wolf_q.push({ -1 * dp_wf[next],next, false });
                }
            }
            else { //늑대가 느리게 갈때는 가중치 2배로 해서 더해줌
                int next = i.first;
                if (dp_wf[now] + (i.second * 2) < dp_ws[next]) {
                    dp_ws[next] = dp_wf[now] + (i.second * 2);
                    wolf_q.push({ -1 * dp_ws[next],next, true });
                }
            }
        }
    }
    //늑대 다익스트라
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dp_f[i] < min(dp_wf[i], dp_ws[i])) ans++;
    }
    printf("%d", ans);
}