백준 16118 - 달빛 여우, C++ ,BFS

16118번: 달빛 여우

#include <iostream>
#include <queue>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;

// slow wolf <(*2) normal fox <(*2) fast wolf

int n, m;
int foxCost[4001];
int wolfCost[2][4001];
vector<pair<int, int>> edges[4001];

void FoxRunning(){
    priority_queue<pair<int, int>> q;   //  cost, current pos
    q.push(make_pair(0, 1));
    foxCost[1] = 0;

    while(!q.empty()){
        int cur = q.top().second;
        int cost = -q.top().first;
        q.pop();

        if(foxCost[cur] < cost)
            continue;

        for(unsigned i = 0; i < edges[cur].size(); i++){
            int next_pos = edges[cur][i].first;
            int next_cost = cost + edges[cur][i].second;

            if(next_cost < foxCost[next_pos]){
                foxCost[next_pos] = next_cost;
                q.push(make_pair(-next_cost, next_pos));
            }
        }
    }
}

void WolfRunning(){
    priority_queue<pair<int, pair<int, int>>> q;    // cost, current pos, cur state
    // start with running state (=0)
    q.push(make_pair(0, make_pair(1, 0)));
    // wolfCost[0][1] = 0;

    while(!q.empty()){
        int cur = q.top().second.first;
        int cost = -q.top().first;
        int cur_state = q.top().second.second;
        q.pop();

        int prev_state = (cur_state == 1) ? 0 : 1;
        if(wolfCost[prev_state][cur] < cost)
            continue;

        for(unsigned i = 0; i < edges[cur].size(); i++){
            int next_pos = edges[cur][i].first;
            if(cur_state == 0){
                // state = running
                int next_cost = cost + edges[cur][i].second / 2;

                if(next_cost < wolfCost[0][next_pos]){
                    wolfCost[0][next_pos] = next_cost;
                    q.push(make_pair(-next_cost, make_pair(next_pos, 1)));
                }
            }
            else{
                // state = walking
                int next_cost = cost + edges[cur][i].second * 2;

                if(next_cost < wolfCost[1][next_pos]){
                    wolfCost[1][next_pos] = next_cost;
                    q.push(make_pair(-next_cost, make_pair(next_pos, 0)));
                }
            }
        }
    } 
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(unsigned i = 0; i < 4001; i++){
        foxCost[i] = INT_MAX;
        wolfCost[0][i] = INT_MAX;
        wolfCost[1][i] = INT_MAX;
    }

    // input
    cin >> n >> m;
    for(unsigned i = 0; i < m; i++){
        int from, to, cost;
        cin >> from >> to >> cost;

        edges[from].push_back(make_pair(to, cost*2));
        edges[to].push_back(make_pair(from, cost*2));
    }

    // Djikstra
    FoxRunning();
    WolfRunning();
    
    int wolf_win_count = 0;
    for(unsigned i = 2; i <= n; i++){
        if(foxCost[i] < min(wolfCost[0][i], wolfCost[1][i]))
            wolf_win_count++;
    }

    cout << wolf_win_count << endl;
    return 0;
}

---

기존 BFS 에서 생각해야 하는 점들이 좀 있는 문제였습니다.

 

- 일단 늑대의 빠른 경우를 4의 속도라고 하면 일반적인 여우의 속도는 2, 느린 늑대를 1의 속도를 가지고 있다고 생각한 뒤 입력에서 비용을 2배로 처리해 모두 정수 연산으로 할 수 있게 해줘야 합니다.

- 그리고 여우의 다익스트라와 늑대의 다익스트라를 따로 만들어주고 이에 대한 결과를 다른 배열에 저장하는게 좋습니다.

- 늑대의 비용을 저장할 배열의 경우 2*4001의 크기로 선언을 해준 뒤 0이면은 달릴때의 상태, 1일때 지칠때 상태를 저장해 줬습니다.

+ 처음에 제출을 하고 틀렸을때 wolfCost[0][1] = 0; 를 넣지 말라는 글을 보고 이걸 빼니 통과할 수 있었습니다. 이점에 대해서는 조금 더 생각해 보겠습니다.

 

그리고 정답을 구할 때는 '늑대가 해당 그루터기를 갈 수 있는 가장 빠른 방법'을 선택해야 합니다. 처음에 달린 뒤 바로 달리고, 바로 안달리고 이런거를 고려하는 문제는 아니었습니다.