[백준(파이썬/Python)] 10282_해킹 - 다익스트라

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

10282번: 해킹

 

문제의 조건 중에서

 

"d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다."

 

라는 표현이 있습니다. 이 부분을 주의해서 각 노드(컴퓨터)의 방향성을 정해줘야 합니다. 즉, a에서 b로 방향이 생기는 것이 아니라, b에서 a로 방향이 생기는 것이죠. 

 

이 부분을 처리하고 나면, 문제에서 요구하는 감염된 컴퓨터의 개수와 마지막에 감염된 컴퓨터의 시간을 출력할 때는 1) time리스트에서 inf가 아닌 값들의 개수와 2) inf가 아닌 수 중에서 최대값을 차례대로 출력해주면 됩니다.

 

정답 코드는 아래와 같습니다.

[풀이]

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

def dijkstra(graph, start):
    # 각 컴퓨터가 감염되기까지 걸리는 최단 시간을 기록하는 리스트
    time = [inf] * (n+1)
    time[start] = 0

    # 감염되는 컴퓨터의 개수, 마지막 컴퓨터가 감염되기까지 걸리는 시간
    count, endTime = 0, 0

    pq = []
    heapq.heappush(pq, (0, start))
    while pq:
        curr_time, curr_computer = heapq.heappop(pq)
        if curr_time < time[curr_computer]:
            continue
    
        for next in graph[curr_computer]:
            next_time, next_computer = next[0], next[1]
            # 최단 시간 갱신
            if curr_time + next_time < time[next_computer]:
                time[next_computer] = curr_time + next_time
                heapq.heappush(pq, (curr_time + next_time, next_computer))
    
    for t in time:
        if t < inf:
            count +=1
            # 마지막 컴퓨터가 감염되는 시간
            if t > endTime:
                endTime = t

    return count, endTime


# 테스트 케이스의 개수
tc = int(input())

for _ in range(tc):
    # 컴퓨터 개수, 의존성 개수, 해킹당한 컴퓨터 번호
    n, d, c = map(int, input().split())
    
    graph = [[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        graph[b].append((s, a))
    
    count, endTime = dijkstra(graph, c)
    print(count, endTime)