해킹

문제 설명

해커 yum3이 어느 네트워크 시설의 한 컴퓨터를 해킹했다. 특이하게도 한 컴퓨터가 감염되면 연결되어 있는 다른 컴퓨터도 전염되는 방식인데 웜인가? a가 b라는 컴퓨터에 의존했다면 b 컴퓨터가 감염이 되면 a 컴퓨터 또한 일정 시간 뒤에 전염이 되어 있는 방식이다.

 

yum3이 해킹한 컴퓨터와 각 컴퓨터의 의존성이 주어질 때, 총 몇 대가 감염되고 얼마나 시간이 걸리는지 구하는 문제다.

 

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

10282번: 해킹

문제 풀이

첫 번째 설명

a에서 전체 노드로 넘어가는데, 시간을 구하라. 딱 봐도 다익스트라 문제다. 심지어 다익스트라 문제집에 분류가 되어 있다. 그렇기에 지금까지 해왔던 다익스트라 방식으로 풀면 된다. 나는 이때 우선순위큐를 이용해서 구해줬다. 그리고 현재 노드와 연결된 노드를 확인하기 전에 현재 노드까지의 거리가 dp[node]보다 크다면 continue를 해줬다. 왜냐하면 이는 cost가 최단 거리가 아니라는 의미이기 때문이다.

 

그리고 findWarm으로 감염되지 않는 컴퓨터를 찾는 함수와 lastInfection으로 가장 마지막에 감염된 컴퓨터의 시간을 구해줬다. lastInfection의 경우에는 int(1e9)가 아닐 때만 값을 찾았다. int(1e9)가 dp에 들어있다는 의미는 해당 노드를 거치지 않았다는 것이기 때문이다.

코드

python

import sys
import heapq

t = int(sys.stdin.readline().rstrip())
maxInt = int(1e9)


def dij(start, arr):
    dp = [maxInt for _ in range(n)]
    hq = []
    heapq.heappush(hq, (0, start))
    dp[start] = 0

    while hq:
        cost, node = heapq.heappop(hq)

        if cost > dp[node]:
            continue

        for a in arr[node]:
            aNode, aCost = a
            if dp[aNode] > cost+aCost:
                dp[aNode] = cost+aCost
                heapq.heappush(hq, (dp[aNode], aNode))

    return dp


def findWarm(arr):
    non = 0
    for a in arr:
        if a == int(1e9):
            non += 1
    return non

def lastInfection(arr):
    maxTime = 0
    for a in arr:
        if a != int(1e9):
            if maxTime < a:
                maxTime = a
    return maxTime


for _ in range(t):
    n, d, c = map(int, sys.stdin.readline().rstrip().split(" "))

    graph = [[] for _ in range(n)]
    c -= 1
    for _ in range(d):
        # a가 b를 의존한다. -> b에서 a로 갈 수 있다.
        a, b, s = map(int, sys.stdin.readline().rstrip().split(" "))
        a -= 1
        b -= 1
        graph[b].append([a, s])

    result = dij(c, graph)
    print(n-findWarm(result), lastInfection(result))