[백준10282] / 해킹 - 다익스트라

 

백준10282

 

푼 날짜 : 2024.11.12

푼 문제 : [10282] / 해킹

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근방식 :

일반적인 다익스트라로 풀었다. 

이 문제에서 주의해야할 것은

 

어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다.

 

computer[b].append((a, s))

=> 따라서 b가 감염되어야 a가 감염되므로 위와 같이 작성한다.

 

 

코드 :

import sys
import heapq

T = int(sys.stdin.readline())
for _ in range(T):
    n, d, c = map(int, sys.stdin.readline().split())
    
    computer = [[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        computer[b].append((a, s))
    
    heap = [(c, 0)]
    dist = [float('INF') for _ in range(n+1)]    
    dist[c] = 0

    while heap:
        n_com, n_time = heapq.heappop(heap)

        if dist[n_com] < n_time: continue

        for next, time in computer[n_com]:
            all_time = n_time + time

            if dist[next] > all_time:
                dist[next] = all_time 
                heapq.heappush(heap, (next, all_time))

    ans_com = ans_time = 0
    for i in range(1, n+1):
        if dist[i] != float("INF"):
            ans_com += 1 # 감염된 컴퓨터 수 증가
            ans_time = max(ans_time, dist[i]) # 감염 시간
    
    print(ans_com, ans_time)

 

 

이런 알고리즘은 유형을 잊지 않으려면 비슷한 응용문제를 많이 풀어봐야 한다!

오늘도 1솔 성공 :)