[BOJ 16311] Harry the Hamster

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

 

풀이:

현재 $u$번째 노드에 있다고 할 때; 좌뇌, 우뇌가 시작해서 $t$까지 가는 거리를 각각 $L_u, R_u$라고 합시다.

 

게임이론을 사용하면, 좌뇌는 가장 멀리 가고 싶어하고 우뇌는 가장 가까이 가고싶어하기 때문에 다음 점화식이 성립합니다:

• $L_t = 0, L_u = \max_{u \xrightarrow{w} v} {R_v + w}$
• $R_t = 0, R_u = \min_{u \xrightarrow{w} v} {L_v + w}$
• 여기서 무한루프를 고려하기 위해, $\infty$ 라는 특수한 값을 고려합니다. $r \in \mathbb R$에 대해 $r < \infty$이고, $\infty = r + \infty$ 입니다.

이 점화식을 그대로 사용하면 순환참조 문제가 생깁니다. 이를 위해서, 우리는 하나씩 값이 확정된 것부터 채워나갈 것입니다.

• $L_t = R_t = 0$을 확정짓고, 나머지 $i \ne t$에 대해서는 $L_i = R_i = \infty$에서 시작합니다.
  • $\infty$에서 시작하는 이유는, $t$에서 시작해서 순차적으로 값을 확정짓지 못하는 곳은 무한정 돌 수 있기 때문입니다.
• $L_u$는 $u$에서 나가는 모든 $v$에 대해 $R_v+w$가 확정된 이후에 계산합니다. (확정되지 않으면 값이 $\infty$일 수 있습니다)
• $R_u$는 $u$에서 나가는 모든 $v$가 확정된 이후에 대해서 돌 필요가 없습니다. 다만, $L_v+w$의 최솟값이 확정된 이후에 계산될 수 있습니다. 최솟값을 제외한 다른 $L_v+w$ 값은 무시해도 됩니다.

결국, 우리는 $L_v+w$가 작은 순서대로 값을 채워가면 괜찮다는 것을 알 수 있습니다. Dijkstra's Algorithm과 유사한 방식으로 Priority Queue를 이용해서 관리하면 $R_u$와 $L_u$를 채워갈 수 있습니다. 구체적으로는 다음과 같습니다.

• 확정이 되지 않은 $L_i$와 $R_i$ 중에서 가장 값이 작은 것을 하나 고릅니다.
  • $L_v$를 고를 경우, $u \xrightarrow{w} v$에 대해 $R_u$의 최솟값을 확정하고 싶을 것입니다. $R_u = \min(R_u, L_v + w)$로 계산합니다. 이후 더 작은 값이 들어올 수 있기 때문에, 미확정인 상태로 놔둡니다.
  • $R_v$를 고를 경우, $u \xrightarrow{w} v$에 대해 $L_u$가 정해질 가능성이 있습니다. $u$의 나가는 모든 정점 $u \xrightarrow{x} z$에서 $L_z$값이 정해졌는지 확인합니다. 이제, $R_v = \max_{u \xrightarrow{x} z} L_z + x$로 확정됩니다.
• 이 방법으로 확정되지 않은 값들에 대해서는
  • $L_u$에 대해서는, $u \xrightarrow{w} v$ 중 확정되지 않은 $R_v$가 있기 때문에, 해당 위치에 온 경우 좌뇌는 해당하는 $v$로 갑니다.
  • $R_u$에 대해서는, 모든 $u \xrightarrow{w} v$에 대해 $L_v$가 확정되지 않았기 때문에, 우뇌는 어떤 선택을 하더라도 확정되지 않은 곳으로 갈 수 밖에 없습니다.
  • 좌뇌는 확정되지 않은 값을 계속 탐색하도록 강제할 수 있습니다. 확정되지 않은 값에 목적지가 존재하지 않으므로, 해당 위치에서 시작하면 쥐는 영원히 미로를 돌게 되며 답은 $\infty$ 입니다.

• $L_s$의 값을 적당히 출력해줍니다.

코드: https://www.acmicpc.net/source/share/6e6971f39be441038f7a9fe0e53cadf8