[BOJ]16118번: 달빛 여우

 

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

---

다익스트라 응용문제입니다.

 

달빛 여우는 무난히 다익스트라를 구하면 되겠지만, 문제가 되는 것은 달빛 늑대의 경우입니다.

 

늑대가 하나의 그루터기(노드)에 도착하는 방법은

1. 빠른 속도로 도착하거나 / 2. 느린 속도로 도착하거나 이렇게 두 가지 방법 중 하나로 도착하게 됩니다.

 

그러니 늑대의 경우는 빠르고 / 느리게 움직이는 경우를 모두 dist 배열로 저장해줘야합니다.

 

중요한 건, 우선순위큐에 넣을 자료형과 늑대의 dist를 어떻게 정의할까의 문제입니다.

 

1. 우선순위큐에 넣을 자료형: tuple(long long, int ,int)

튜플의 의미: 현재 노드까지 오는데 걸린 거리 + 다음 탐색 때 늑대의 속도

tuple[0]: 현재 노드까지 도착하는데 지나온 거리의 합

tuple[1]: 현재 노드(그루터기)

tuple[2]: 상태 (SLOW / FAST)

 

예를 들어,

tuple(0,0,FAST)이면, 0번 노드까지 지나온 거리는 0이고, 다음 탐색은 2배로 빠르게 움직인다는 뜻입니다.

tuple(1,5,SLOW)이면, 5번 노드까지 지나온 거리는 1이고, 다음 탐색은 2배로 느리게 움직인다는 뜻입니다.

 

2. 달빛늑대의 dist(dp) 배열: vector<long long> dp[2]

dp의 의미(늑대의 dist)

dp[SLOW][N]: N번째 노드(그루터기)에 느린 속도로 도달한 경우 걸린 총 거리.

-> 다음 탐색은 빠른 속도.

 

dp[FAST][N]: N번째 노드(그루터기)에 빠르 속도로 도달한 경우 걸린 총 거리.

-> 다음 탐색은 느린 속도.

---

그래서 이 두 가지 정보를 가지고 다익스트라를 돌립니다.

 

↓ (이거 처리 안하면 시간초과)

현재 큐에서 뽑은 간선 후보가 이미 dp[이전상태][N]의 거리(간선)보다 크면 얘는 그냥 버리면 됩니다.

 

여기서 중요한 건 현재 뽑은 튜플의 state와 dp의 state는 반대가 되어야 합니다.

이전 상태(dp)에서 느리게 도착했으면 다음 상태(tuple)는 빠르게 갈 수 있는 경우를 따져야 하고,

이전 상태(dp)에서 빠르게 도착했으면 다음 상태(tuple)는 느리게 갈 수 있는 경우를 따져야 합니다.

tlii now = pq.top(); pq.pop();
ll w = -get<0>(now);
int node = get<1>(now);
int state = get<2>(now);

if (w > dp[(state+1)%2][node])
    continue;

 

여기서도 현재 갱신되는 dp의 state와 큐에 새로 들어가는 튜플의 state는 반대가 되어야 합니다.

for (int i = 0; i < graph[node].size(); ++i) {
    int nxt = graph[node][i].first;
    ll weight = graph[node][i].second;

    if (state == FAST) weight /= 2;
    else if (state == SLOW) weight *= 2;

    if (w + weight < dp[state][nxt]) {
        dp[state][nxt] = w + weight;
        pq.push(make_tuple(-dp[state][nxt], nxt, (state + 1) % 2));
    }
}

이렇게 이전에 움직인 상태와 다음에 움직일 상태가 계속 교차해서 나타나게만 해주면 해결할 수 있는 문제입니다. 

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16118.cc