[백준/10979] 가넷이나 버는게 낫지 않아요? (Python)

Problem : https://www.acmicpc.net/problem/10979

10979번: 가넷이나 버는게 낫지 않아요?

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:41:44

 

---

 

문제 설명

 

석주는 유명한 게임 예능 ‘더 찌니어스’의 출연자다. 이 프로그램에서 오늘 ‘징검다리’라는 게임을 하려고 한다. 징검다리의 규칙은 다음과 같다:

 

• N개의 섬과 M개의 양방향으로 통행이 가능한 다리가 그려진 지도가 있다.
• 각 M개의 다리는 건너는데 걸리는 시간이 있다.
• 각 M개의 다리는 건널 때마다 다리별로 정해진 가넷을 받게 된다.
• 모든 플레이어는 1번 섬에서 게임을 시작하며, N번 섬에 도착한 순서대로 플레이어의 순위가 1등, 2등, …이 된다.
• 1번 섬에서 N번 섬으로 가는 경로는 항상 존재한다.
• 어떤 플레이어가 이용한 다리의 순서와 완전히 똑같은 순서로 다른 플레이어가 다리를 이용할 수 없다.

 

오늘의 방송에서 석주는 다른 ‘더 찌니어스’의 출연자인 영석이와 비밀스럽게 연합을 맺었다! 오늘 석주는 영석이에게 1등을 내어주고, 2등으로 들어오는 전략을 짜려고 한다. (단, 공동 1등인 경우 2등을 했다고 인정한다.) 영석이는 가넷과 관계 없이 1등만 하면 된다는 생각을 하는 반면, 석주는 개당 현금 100만원의 가치를 갖는 가넷을 최대한 많이 모으려고 한다. 영석이와 석주는 다른 플레이어보다 먼저 경로를 선택할 기회를 갖고 있다.

이러한 방법으로 플레이 했을 때, 석주가 2등으로 N번 섬에 도착할 때까지 걸리는 시간과 그 때 모을 수 있는 가넷의 수는 얼마나 될까? 

 

입력 및 출력

 

입력

 

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 섬의 수 N(1 ≤ N ≤ 50000)과 다리의 수 M(1 ≤ M ≤ 200,000)가 주어진다.
각 테스트 케이스의 두 번째 줄부터 M+1번 줄까지 32비트 정수 x, y, t, g (1 ≤ x, y ≤ N, t, g는 1보다 큰 32비트 부호 있는 정수)가 주어진다. 이는 x에서 y로 가는 다리가 있으며, 다리를 건너는 데에 걸리는 시간은 t, 얻을 수 있는 가넷의 수는 g임을 의미한다. 

 

출력

 

i번째 테스트 케이스에서 석주가 t시간에 게임을 마치며 g가넷을 얻을 경우, “Game #i: Suckzoo ends game in time t, earning g garnet(s).”를 출력한다.

 

입력 예시

 

3
4 5
1 2 1 1
1 3 1 2
1 4 1 1
2 4 1 1
3 4 1 2
2 2
1 2 1 1
1 2 1 99
3 2
1 2 1 1
2 3 99 1

 

출력 예시

 

Game #1: Suckzoo ends game in time 2, earning 4 garnet(s).
Game #2: Suckzoo ends game in time 1, earning 99 garnet(s).
Game #3: Suckzoo ends game in time 102, earning 4 garnet(s).

 

 

---

 

풀이

 

영석, 석주를 순서대로 다익스트라로 풀이해보자.

 

• 영석은 (최소 시간, 최소 가넷)을 우선순위로 다익스트라 알고리즘을 진행한다. 이 때, 갱신되는 dist 배열에 최종적으로 이용한 edge를 기록해 둔다. 탐색이 종료되면, 최종 최소 경로를 앞서 기록한 edge 정보를 토대로 저장한다. 이 edge 정보를 가지고 석주는 자신의 경로가 영석과 완전히 겹치는지 판단하게 된다.
  • 예제의 2번의 경우 영석은 가넷 1, 석주는 가넷 99를 가져감을 알 수 있다. 즉 공동 1등일 때, 영석은 적은 가넷을 가져가야만 한다. 따라서 영석의 가넷은 최소 가넷을 기준으로 정해둘 필요가 있다.
• 석주는 (최소 시간, 최대 가넷)을 우선순위로 다익스트라 알고리즘을 진행한다. 이 때 dist 배열은 ( N , 2)의 2차원 배열이 되며, 앞서 저장한 영석과의 경로 겹침 여부를 저장하게 된다. 경로가 겹치지 않고, 또한 최소 시간 내에 N에 도달할 수 있었을 경우 확실한 2등이므로 탐색을 종료한다.

우선순위 큐를 이용한 다익스트라 알고리즘을 2번 사용하였으므로 시간복잡도는 그대로 O(ElogV)가 된다.

 

 

풀이 코드

from collections import defaultdict
from heapq import *
import sys
input = sys.stdin.readline
MAX = float('inf')

def dijkstra_youngsuk(edges, N) :
  dist = [(MAX, MAX, -1, -1)]*(N+1)
  dist[1] = (0, 0, 1, 0)
  q = [(0, 0, 1)]
  while q :
    t, g, n = heappop(q)
    if n == N :
      break
    for i, (_t, _g, x, _) in enumerate(edges[n]) :
      if dist[x] > (t + _t, g + _g, n, i) :
        dist[x] = (t + _t, g + _g, n, i)
        heappush(q, (t + _t, g + _g, x))
  n = N
  while n != dist[n][2] :
    n, i = dist[n][2], dist[n][3]
    edges[n][i][-1] = 1

def dijkstra_suckzoo(edges, N) :
  dist = [[(MAX, 0)]*2 for _ in range(N+1)]
  dist[1][1] = (0, 0)
  q = [(0, 0, 1, 1)]
  while q :
    t, g, matched, n = heappop(q)
    g = -g
    if n == N and not matched :
      return t, g
    for _t, _g, x, m in edges[n] :
      if dist[x][matched & m] > (t + _t, -g - _g) :
        dist[x][matched & m] = (t + _t, -g - _g)
        heappush(q, (t + _t, -g - _g, matched & m, x))

def solve(i) :
  N, M = map(int, input().split())
  edges = defaultdict(list)
  for _ in range(M) :
    x, y, t, g = map(int, input().split())
    edges[x].append([t, g, y, 0])
    edges[y].append([t, g, x, 0])

  dijkstra_youngsuk(edges, N)
  t, g = dijkstra_suckzoo(edges, N)
  print("Game #{}: Suckzoo ends game in time {}, earning {} garnet(s).".format(i+1, t, g))

T = int(input())
for i in range(T) :
  solve(i)

풀이 완료!