[백준] 10282번 해킹 파이썬

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 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)가 두 번 이상 존재하지 않는다.

출력

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

예제 입력 1

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

예제 출력 1

2 5
3 6

제출답안

1. 다익스트라를 수행하기 위해 함수를 생성한다.
   1. 먼저 heap을 수행하기 위한 큐 q 변수를 생성한다.
   2. 해당 힙에 start 노드와 거리를 넣는다.
   3. 해당 노드의 거리는 start 이기 때문에 0이므로 0으로 지정한다.
2. q에 값이 없을 때까지 while을 돈다.
   1. q 에서 거리가 가장 가까운 값(맨 앞의 값)을 꺼내서 dist 와 node 에 각각 할당한다.
      1. 만약에 distance에 node 값이 dist 보다 작으면 그 노드는 이미 작업이 완료된 노드이기 때문에 다음으로 넘어간다.
   2. graph에서 node에 저장된 값들을 꺼내서 for loop를 돈다.
      1. dist와 현재 노드에서 꺼낸 값의 시간(s)을 더하여 cost에 할당한다.
      2. 만약 cost가 distance에 저장된 지금의 노드의 값(i[0])보다 작으면 cost로 변경하고 q에 삽입한다.
   3. 감염수와 시간을 각각 0으로 할당한다.
      1. distance를 for loop 돈다.
      2. 만약에 해당 노드가 무한대가 아니라면 그 컴퓨터는 감염된 것이기 때문에 cnt에 1을 더하고 sec에 max 로 시간을 할당한다.
         1. max인 이유는 heapq에서 시간이 적은것들이 먼저 pop되어서 계산되었기 때문에 마지막 컴퓨터일수록 시간이 길게 걸리기 때문이다.
3. 최종제출할 답안 함수를 생성한다.
   1. t를 입력받도 t 만큼 while을 돈다.
      1. 문제에서 말하는 것과 같이 변수명을 설정하고 각각 할당한다.
      2. graph와 distance를 각각 초기화 한다.
      3. d만큼 돌면서 의존성 컴퓨터와 s를 graph에 append한다.
   2. dijkstra수행 후 t에서 1을 뺀다.
      1. t만 적어놓은 이유는 0이면 False로 인식해서 while이 종료된다.

import heapq
import sys

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

# 1
def dijkstra(start, distance, graph):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    # 2
    while q:
        # 2-1
        dist, node = heapq.heappop(q)
        if distance[node] < dist:
            continue
        # 2-2
        for i in graph[node]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    # 2-3
    cnt, sec = 0, 0
    for i in distance:
        if i != INF:
            cnt += 1
            sec = max(sec, i)
    print(cnt, sec)

# 3
def solution():
    t = int(input())
    # 3-1
    while t:
        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))
        # 3-2
        dijkstra(c, distance, graph)
        t -= 1


solution()