[백준/Python3] 29687번 : Игра

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

29687번: Игра

---

알고리즘 분류

• 그래프 이론
• 데이크스트라
• 최단 경로

문제

Два игрока играют в новую настольную игру. На поле для игры есть города и дороги между ними, причем дороги между разными городами могут иметь различную длину. При этом, если длина дороги между двумя городами равна
$x$, то на этой дороге в ряд находятся 
$(x - 1)$ деревень, можно перейти от города к крайней деревне на дороге, от этой деревне к соседней, и т. д.
У каждого их игроков есть по фишке, исходно фишки игроков расположены в некоторых различных городах. Игроки ходят по очереди: за один ход можно передвинуть фишку в город или деревню, которые соединены с текущей вершиной напрямую, либо можно оставить фишку на месте. Начинает первый игрок.
Однако есть одно ограничение: если один из игроков находится в одной из деревень на дороге между двумя городами, то другой не может переходить ни в одну деревню, находящуюся на этой дороге.
Цель каждого из игроков заключается в том, чтобы добраться в столицу первым.

두 명의 플레이어가 새로운 보드 게임을 하고 있습니다. 경기장에는 도시와 도시 사이에 도로가 있으며, 도시마다 도로의 길이가 다를 수 있습니다. 또한 두 도시 사이의 도로 길이가 x라면 이 도로에는 (x-1)개의 마을이 연속적으로 있으므로 도시에서 도로의 가장 바깥쪽 마을로, 이 마을에서 이웃 마을로 갈 수 있습니다.

각 플레이어는 칩을 가지고 있으며, 처음에는 플레이어 칩이 다른 도시에 위치합니다. 플레이어는 차례대로 진행합니다. 한 번의 이동으로 조각을 현재 정점에 직접 연결된 도시나 마을로 이동할 수도 있고 조각을 제자리에 둘 수도 있습니다. 첫 번째 플레이어가 시작됩니다.

그러나 한 가지 제한 사항이 있습니다. 플레이어 중 한 명이 두 도시 사이의 도로에 있는 마을 중 하나에 있으면 다른 플레이어는 이 도로에 있는 어떤 마을에도 갈 수 없습니다.

각 플레이어의 목표는 수도에 먼저 도착하는 것입니다.

 

입력

입력 파일의 첫 번째 줄에는 두 개의 숫자 n --- 도시 수와 m --- 도로 수(1 =< n,m=< 10^5)가 포함됩니다.
다음 m개 줄에는 세 개의 숫자 a, b, c가 포함되어 있습니다. 이는 도시 a와 b 사이에 c - 1개의 마을(a=!b, 1=< c=< 10^9)을 포함하는 c 길이의 도로가 있음을 의미합니다.
마지막 줄에는 세 개의 숫자 s_1, s_2--- 플레이어의 조각이 처음 위치한 도시의 번호(s_1 != s_2) 및 t --- 수도인 도시의 번호가 포함됩니다.
모든 도시의 도로가 다른 도시로 연결될 수 있다는 것이 보장됩니다.

출력

출력 파일에서 첫 번째 플레이어가 해당 항목에 도달하면 First를 인쇄합니다. 대문자가 먼저이고, 두 번째이면 Second입니다.

예제 입출력

---

풀이

개인적으로 꽤 오랜시간 걸려서 풀었던 문제다. 혼자서 풀다가 안 풀려서 도움도 청하고, 그 풀이를 보며 재구성해서 다시 풀어냈다.

(s1)1--3-4(s2)
           | 
          2(t)


플레이어들이 각자 수도로 오는게 아니라 역으로 수도에서 출발해서 도시로 가게 시키면 된다는 것이 이 문제의 아이디어가 된다. 이렇게 재구성하면 중복해서 길을 못 지나간다는 조건을 고려할 필요가 없어지고, 거꾸로 가서 ( 먼저 도착 -> 먼저 도착한 플레이어 승자 /  동시 도착시 -> 플레이어 1의 무조건 승 )으로만 케이스를 구분지어주면 된다.

---

코드

import heapq
import sys

# 다익스트라
def dijkstra(s): 
    # 거리 리스트 무한대로 초기화
    distances = [float('inf') for _ in range(N+1)]
    # 우선순위 큐 -> 최단거리 찾기
    hq = []
    # 시작 점은 0
    heapq.heappush(hq, (0, s))
    distances[s] = 0 

    while hq: # 모든 노드에 대해 순회
        dist, now = heapq.heappop(hq)
        if distances[now] < dist: # 거리가 이미 더 짧음
            continue # 무시
        for i in road[now]: # 인접 노드 순회
            next_node = i[0]
            cost = dist + i[1]
            if cost < distances[next_node]: # 새로 계산한게 기존보다 짧음
                distances[next_node] = cost # 갱신
                heapq.heappush(hq, (cost, next_node)) # 추가
    return distances

# 도시, 거리
N, M = map(int,sys.stdin.readline().rstrip().split())
# 도시의 연결 상태&거리 저장
road = [[] for _ in range(N+1)]

for _ in range(M):
    # 도시1, 도시2, 마을갯수
    a,b,c = map(int,sys.stdin.readline().rstrip().split())
    road[a].append((b,c)) # 도로 양 쪽으로 다 갈 수 있음
    road[b].append((a,c))

# road =[[(3, 2)], [(3, 3)], [(1, 2), (2, 3), (4, 1)], [(3, 1)]]

# s1 플1 s2 플2 t 수도
s1, s2, t = map(int,sys.stdin.readline().rstrip().split())
 
distances= dijkstra(t)

if distances[s1]<=distances[s2]:
    print("First")
else:
    print("Second")