[Python] 백준 10282번 해킹

문제

10282번: 해킹

입력

• 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
  • 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
  • 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.
• 각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

출력

• 각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

입력 예제

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4

출력 예제

2 5
3 6

문제 풀이

• b가 감염되면 그로부터 일정 시간 뒤 a도 감염되므로 그래프[b]번째 인덱스에 a와 해킹당하는 시간을 넣는다.
• 다익스트라 알고리즘을 수행하여 해킹당하는 시간을 계산한다.
• 해킹당한 컴퓨터 수에 시작하는 컴퓨터도 포함 해야하므로 INF보다 작고, 0보다 큰 경우의 개수를 센다.
• 그 후, INF보다 작은 최댓값을 찾아 컴퓨터의 수와 해킹당하는 시간을 출력한다.

코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, c))
    distance[c] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

for _ in range(int(input())):
    # 컴퓨터 수, 의존성, 해킹당한 컴퓨터
    n, d, c = map(int,input().split())
    graph = [[] for _ in range(n + 1)]
    distance = [INF] * (n + 1)
    for _ in range(d):
        a, b, s = map(int,input().split())
        graph[b].append((a, s))

    result = dijkstra(c)
    cnt = 0
    max_val = 0
    for i in result:
        if i < INF:
            if i >= 0:
                cnt += 1
            if max_val < i:
                max_val = i
    print(cnt, max_val)