[백준] 10282번 - 해킹 (파이썬)

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

# 해킹
import heapq
import sys
input = sys.stdin.readline


def hacking(n, start):
    dist = [sys.maxsize] * (n+1)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        time, computer = heapq.heappop(q)
        for ntime, ncom in arr[computer]:
            total = time + ntime
            if dist[ncom] > total:
                dist[ncom] = total
                heapq.heappush(q, (total, ncom))
    result_time = 0
    result_com = 0
    for x in dist:
        if x != sys.maxsize:
            result_com += 1
            result_time = max(result_time, x)
    return [result_com, result_time]


T = int(input())
for _ in range(T):
    n, d, c = map(int, input().split())
    arr = [[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        arr[b].append((s, a))
    print(*hacking(n, c))

 

최단거리, 다익스트라
1. 의존성에 맞춰서 입력을 받는다. (arr[b].append((s, a)) => a가 b를 의존)
2. hacking(n, c) : n개의 컴퓨터 중, c컴퓨터에서 부터 해킹 시작
    - start에서 각 컴퓨터까지의 거리를 dist리스트로 표현
    - dist를 최소값으로 업데이트 (heapq를 이용)
    - dist에서 maxsize가 아닌 값들 마다 result_com++, dist에서 해당 거리 값 중 가장 큰 값을 result_time으로
   - return [result_com, result_time]
3. 출력