[백준 10282번] 해킹 문제 풀이

 

< 문제 >

 

 

 

 

< 입출력 >

 

 

 

 

 

< 풀이 >

'이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다' 라는 문구에서 방향이 있는 그래프임을 알 수 있다.

테스트 케이스의 크기만큼 반복하여, 다익스트라 알고리즘을 이용해 개수와 최대값을 구하면 감염된 컴퓨터의 개수와 모두 감염되는데 걸리는 시간을 구할 수 있다.

 

 

 

 

 

< 코드 > 

import sys
import heapq

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

test_num = int(input())

def dijkstra(start):
    q = []
    distance = [INF] * (n + 1)

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for node_index, node_cost in graph[now]:
            cost = dist + node_cost

            if distance[node_index] > cost:
                distance[node_index] = cost
                heapq.heappush(q, (cost, node_index))

    return distance

for j in range(test_num):

    # 노드의 개수, 간선의 개수 입력 받기
    n, m, x = map(int, input().split())
    # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기
    graph = [[] for i in range(n + 1)]

    # 모든 간선 정보를 입력 받기
    for _ in range(m):
        a, b, c = map(int, input().split())  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
        graph[a].append((b, c))

    cnt = 0
    ans = 0
    dp = dijkstra(x)
    for i in dp:
        if i != INF:
            cnt += 1
            ans = max(ans, i)

    print(cnt, ans)