백준 10282 : 해킹 (Python)

본문 링크

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

def Dijkstra(start):

    dp=[INF]*(N+1) ; dp[start]=0

    heap=[] ; heapq.heappush(heap,(0,start))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:
            next_value+=value

            if next_value<dp[next_node]:
                dp[next_node]=next_value
                heapq.heappush(heap,(next_value , next_node))

    dp.sort()
    for i in range(len(dp)-1,-1,-1):
        if dp[i]!=INF:
            return i+1,dp[i]

for i in range(int(input())):

    N,D,C=map(int,input().split()) # 컴퓨터의 개수 , 의존성의 개수 , 해킹당한 컴퓨터의 번호(시작점)

    graph=[ [] for _ in range(N+1) ]

    for j in range(D):
        a,b,s=map(int,input().split())
        graph[b].append((s,a)) # 단방향.

    print(*Dijkstra(C))

📌 어떻게 접근할 것인가?

다익스트라 응용 문제입니다.
시작노드에서 모든 노드들에 대해 최단경로를 구해줍니다.
이후 최단경로를 모두 구했다면 그것을 담은 배열을 정렬해줍니다.

문제에서 요구하는 바는 가능한 모든 컴퓨터들을 해킹했을때 그때의 개수와 시간이므로
정렬을 해서 뒤에서부터 dp 의 값이 INF 가 아닐때까지 찾습니다.
즉 해킹을 한 컴퓨터중에서의 최대값을 찾습니다.

그리고 반복문을 통해서 찾았으므로 그때의 인덱스 값은 바로 해킹한 컴퓨터의 수가 됩니다.

따라서 return i+1 , dp[i] 를 사용했습니다.