10282. 해킹 (Python)

10282번: 해킹

 

풀이

 다익스트라를 사용하여 문제를 해결할 수 있다. 입력으로 주어지는 의존성은 그래프에서 방향성이 있는 간선이라고 생각하면 된다. 예를 들어 1, 2, 3이라는 의존성이 주어지면 2번에서 1번으로 가는 비용이 3인 간선인 것이다.

 

 예제에서 주어진 케이스 중 두 번째 케이스를 보자. 이를 그래프로 표현하면 다음과 같다. 

 처음에 1번 컴퓨터가 감염되어있고 의존성에 따라 다른 컴퓨터로 전염되기 시작한다. 먼저 1번 컴퓨터에서 2번 컴퓨터로 전염되는데 2초의 시간이 걸린다. 그리고 1번에서 3번으로 바로 갈 수도 있으나 이제 2번 컴퓨터도 감염되었으므로 의존성에 따라 2번에서 3번으로 전염이 진행된다. 1번에서 3번으로 바로 전염되면 총 8초의 시간이 걸리나 먼저 2번으로 전염된 후 3번으로 전염되면 총 6초의 시간이 걸린다. 마지막으로 3번 컴퓨터가 전염되는 최초의 시간은 6초인 것이다. 

 

 이와 같이 처음 감염되어 있는 컴퓨터를 시작점으로 다익스트라를 통해서 각 컴퓨터까지의 최단 거리를 구해준다. 그 후 그래프에 따라 시작점에서 도달할 수 있는 총컴퓨터의 개수와 그중 가장 오래 걸린 시간을 찾아서 이를 출력해 주면 된다. 

 

코드

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')


# 해킹당한 컴퓨터를 시작으로 다익스트라
def dijkstra(start):
    dist = [INF for _ in range(N+1)]
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        time, nowComputer = heapq.heappop(q)

        if dist[nowComputer] < time:
            continue

        for nextComputer, nextTime in graph[nowComputer]:
            totalTime = time + nextTime

            if totalTime < dist[nextComputer]:
                dist[nextComputer] = totalTime
                heapq.heappush(q, (totalTime, nextComputer))

    return dist


if __name__ == '__main__':
    T = int(input())

    for _ in range(T):
        # 컴퓨터 개수, 의존성 개수, 해킹당한 컴퓨터 번호
        N, D, C = map(int, input().split())
        graph = [[] for _ in range(N+1)]  # 의존성 그래프

        for _ in range(D):
            # b에서 a로 향하는 간선
            a, b, s = map(int, input().split())
            graph[b].append((a, s))

        dist = dijkstra(C)

        # 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간
        virusCount, resTime = 0, 0
        for i in range(1, N+1):
            if dist[i] != INF:  # C에서 시작하여 도달할 수 있는 컴퓨터라면
                virusCount += 1  # 감염되는 컴퓨터의 수를 증가시키고
                # 가장 오래 걸리는 시간을 찾아 resTime을 갱신한다.
                resTime = max(resTime, dist[i])

        print(virusCount, resTime)