[Python | 10282] 해킹

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

---

문제 설명

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

 

📌 시간 제한: 2초

---

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

---

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

---

문제 접근

이 문제는 한 컴퓨터 c에서 시작된 해킹이 의존성(“b가 뚫리면 a도 s초 뒤에 뚫린다”)을 따라 퍼질 때, 최종적으로 감염되는 컴퓨터의 수와 마지막 감염 시각을 구하는 문제다. 이때 의존 관계가 A→B(“B가 해킹되면 A가 해킹된다”)로 주어지므로, 간선 방향을 반대로 뒤집어 B→A 형태의 인접 리스트를 구성하고, 시작점 C에서 출발하여 각 컴퓨터가 해킹되는 최소 시간을 구하는 최단 경로 문제로 바꿔 풀었다. 모든 간선의 가중치(해킹 전파 시간)가 양수이므로, 우선순위 큐를 활용한 다익스트라 알고리즘이 자연스럽게 어울린다.

 

핵심은 간단하다. 감염 전파 시간을 가중치가 있는 최단 경로로 해석하고, 방향을 올바르게 맞춘 뒤 다익스트라를 돌리면 된다. 즉, 입력에서 (a b s)를 받으면 그래프를 b→a 가중치 s로 저장한다. 이렇게 하면 “c에서 시작해 각 정점까지의 최소 감염 시간”이 그대로 다익스트라의 결과가 된다.

 

간선을 뒤집은 뒤 문제를 바라보면, 시작점 c에서 다른 정점까지 도달하는 최소 시간을 구하는 단일 출발 최단 경로(SSSP) 문제로 환원된다. 간선 가중치가 모두 양수이므로 음수 간선이나 음수 사이클을 고려할 필요가 없다. SSSP를 해결하는 대표 알고리즘으로는 벨만–포드, 0-1 BFS, 다익스트라가 있는데, 가중치가 임의의 양수이고 정점·간선 수가 최대 10⁵ 수준임을 감안하면 우선순위 큐 기반 다익스트라가 가장 빠르고 간단하다. 0-1 BFS는 가중치가 0 또는 1일 때만 유효하고, 벨만–포드는 O(N D)라서 불필요하게 느리다.

 

다익스트라를 한 번 수행하면 배열 dist에 “컴퓨터 v가 처음 감염되는 최소 시각”이 저장된다. dist 값이 무한대(INF)가 아닌 정점은 실제로 감염된 컴퓨터이므로, 그 개수를 세면 감염된 컴퓨터 수를 얻는다. dist 배열 가운데 최댓값은 가장 늦게 감염된 시각이 된다. 만약 c만 감염되는 경우를 대비해 dist에서 유한한 값이 하나뿐이어도 최댓값은 자연스럽게 0이거나 s가 되므로 별도 예외 처리가 필요하지 않다.

 

시간 복잡도는 정점 N, 간선 D인 그래프에서 다익스트라가 (N + D) log N에 동작한다. 입력에 테스트케이스가 T개 주어지므로 전체 복잡도는 T·(N + D) log N이다. N과 D가 10⁴에서 10⁵ 수준으로 커지더라도 log N이 완만하게 증가하므로 실행 시간은 충분히 여유롭다. 메모리 사용은 인접 리스트와 거리 배열을 합쳐 O(N + D)로, 문제 제한 안에서 무리가 없다.

---

구현

• 힙에서 꺼낸 (t, u)가 이미 기록된 거리보다 크면 버리고, 그렇지 않으면 모든 인접 정점 v에 대해 nt = t + w를 계산해 더 짧으면 갱신·푸시
• 힙에 같은 정점이 여러 번 들어갈 수 있으므로 if dist[u] < t: continue 절로 낡은 경로를 즉시 건너뜀
• 탐색이 끝나면 dist[v] < INF인 정점의 개수가 감염된 컴퓨터 수이고, 그 중 최대값이 마지막 감염 시각

import sys
import heapq
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    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((a, s)) # b가 해킹되면 s초 후 a가 해킹된다

    INF = float('inf')
    dist = [INF] * (n+1) # 거리 배열 무한대 초기화
    dist[c] = 0

    pq = [(0, c)]
    while pq:
        t, u = heapq.heappop(pq)
        if dist[u] < t:
            continue
        for v, w in graph[u]:
            nt = t + w
            if dist[v] > nt:
                dist[v] = nt
                heapq.heappush(pq, (nt, v))

    infected = sum(1 for x in dist[1:] if x < INF)
    last_time = max((x for x in dist[1:] if x < INF), default=0)
    print(infected, last_time)