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

www.acmicpc.net/problem/16118

16118번: 달빛 여우

 

 

 

알고리즘 종류

다익스트라

 

 

 

사고 과정

늑대가 움직이는 것이 주목해야 할 부분입니다. '속력 = 거리 / 시간' 공식이 있습니다. 속력이 2배 빠르다는 것은 거리가 같을 때 시간이 1/2배 된다는 것이고, 속력이 1/2배 빠르다는 것은 거리가 같을 때 시간이 2배 된다는 것입니다. 따라서, 늑대가 빠르게 달릴 때는 거리 가중치에 1/2배를 해주고, 늑대가 느리게 달릴 때는 거리 가중치에 2배를 해주면 됩니다. 

 

그리고 늑대의 경우 노드에 도착할 때, 달려서 오거나 걸어서 오는 2가지 경우가 있기 때문에 DP 테이블을 2개 만들어 줍니다.

 

또 하나 주목할 점이 있습니다. 시작점을 0으로 초기화 하지 않습니다. 왜냐하면, 노드 1에서 출발하여 다시 노드 1로 돌아온 다음에 노드 A에 도착하는 것이 더 빠를 때까 있기 때문입니다. 아래 이미지로 보겠습니다.

 

시작 노드 1에서 노드 3까지 이동을 기록했습니다. 

 

자 그러면 시작 노드 1을 초기화 하지 않고 해보겠습니다. 우선, 노드 1에서 출발해서 노드 1로 돌아오는 과정입니다. 뛰기 -> 걷기 -> 뛰기를 거쳐서 가중치 18이 되었습니다. 이 값음 INF vs 18을 해서 더 작은 값으로 18이 된 것입니다. 이상태에서 3으로 가겠습니다. 

 

아래와 같이 노드 3에 뛰어서 도착하면 가중치 122이 됩니다. 따라서 걸어서 도착한 401과 122를 비교해서 122가 더 최소인 것을 알 수 있습니다. 그러면, 시작 노드 1을 0으로 초기화 해서 해보겠습니다.

 

아래와 같이 이동을 1->5->4를 하고 노드 1로 올 때 가중치를 비교합니다. 시작 노드가 1로 초기화 되어 있으면 당연히 Queue에 넣어줄 수 없습니다. Queue에 넣어 줄 수 없으면 위 이미지에서 얻은 122값을 구할 수 없습니다. 따라서 시작 노드 1을 0으로 초기화 하지 않습니다.

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define MAX 987654321
 
using namespace std;
 
int n, m;
 
int Fdist[4001];
int Wdist[2][4001]; // 걸어서 또는 뛰어서 노드 v에도 도착한 최단 시간  
 
vector<vector<pair<int, int> > > edges;
 
void Fox_dijkstra(){
    
    priority_queue<pair<int, int> > pq;
    pq.push({0, 1});
    Fdist[1] = 0;
    
    while(!pq.empty()){
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
        
        if(Fdist[here] < cost) continue;
        
        for(int i=0; i<edges[here].size(); i++){
            int next = edges[here][i].first;
            int next_cost = cost + edges[here][i].second;
            
            if(Fdist[next] > next_cost){
                Fdist[next] = next_cost;
                pq.push({-next_cost, next});
            }
        }
    }
}
 
 
void Wolf_dijkstra(){
    
    priority_queue<pair<int, pair<int, int> > > pq; // dist, node, state(0: walk/ 1: run)
    pq.push({0, {1, 1}});
    
    while(!pq.empty()){
        int here = pq.top().second.first;
        int cost = -pq.top().first;
        int state = pq.top().second.second; // 현재 노드에서 다음 노드까지  걸어갈지 뛰어갈지 상태  
        pq.pop();
        
        // 현재 상태가 뛰어서 다음 노드로 간다면, 이전에 걸었다는 의미
        // 따라서 걸어서 도착한 최소 비용이 저장된 값(Wdist) VS 걸어서 도착한 비용(cost) 비교  
        if(Wdist[(state+1)%2][here] < cost) continue; 
        
        for(int i=0; i<edges[here].size(); i++){
 
            if(state==1){
                int next = edges[here][i].first;
                int next_cost = cost + edges[here][i].second/2;
                
                if(Wdist[1][next] > next_cost){
                    Wdist[1][next] = next_cost;
                    pq.push({-next_cost, {next, 0}});
                }
            }
            else if(state==0){
                int next = edges[here][i].first;
                int next_cost = cost + edges[here][i].second*2;
                
                if(Wdist[0][next] > next_cost){
                    Wdist[0][next] = next_cost;
                    pq.push({-next_cost, {next, 1}});
                }
            }
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    edges.resize(n+1);
    
    int u, v, w;
    for(int i=0; i<m; i++){
        cin >> u >> v >> w;
        
        edges[u].push_back({v, w*2});
        edges[v].push_back({u, w*2});
    }
    
    for(int i=1; i<=n; i++) {
        Fdist[i] = MAX;
        Wdist[0][i] = MAX;
        Wdist[1][i] = MAX;
    }
    
    Fox_dijkstra(); // Fox
    Wolf_dijkstra(); // Wolf
    
    int answer = 0;
    for(int i=2; i<=n; i++){
        if(Fdist[i] < min(Wdist[0][i], Wdist[1][i])) answer ++;
    }
    
    cout << answer << endl;
}

 

 

 

시행착오

시작 노드 1을 0으로 초기화하는 것 때문에 2시간을 소모했습니다. 이전까지 경험한 다익스트라 문제는 시작노드를 대부분 0으로 초기화 했기 때문에 경험에 기반하여 저도 모르게 행동했습니다. 이후 질문 글을 읽다가 초기화가 원인일 수 도 있다고 생각해서 수정한 뒤에 제출할 수 있었습니다. 걷기와 뛰기 라는 2가지 경우가 있기 때문에 시작 노드를 지나서 더 작은 최단 거리가 나올 수 있다는 것을 배울 수 있었습니다.

 

또 하나 방해했던 부분은 시간초과입니다. 아래 코드입니다.

 

if(Wdist[(state+1)%2][here] < cost) continue; 

 

(state+1) % 2을 해줘야 하는 것을 몰랐습니다. PQ에서 꺼냈을 때 state는 현재 노드에서 걷기/뛰기로 출발하겠다는 의미입니다. 따라서 그 반대 경우 뛰기/걷기로 DP 테이블에서 cost와 현재 노드까지 온 cost를 비교할 수 있습니다.