백준 10282번 <해킹>

백준 알고리즘 10282번

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

10282번: 해킹

---

10282번

컴퓨터 하나를 해킹했을 때, 몇 대의 컴퓨터를 해킹할 수 있는지 찾고 얼마나 시간이 걸리는지 구해라

 

입력으로 첫 줄에 테스트케이스의 수 testcase가 주어진다.

각 테스트케이스는 

첫 줄에는 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다,

이어서 d개의 줄에 컴퓨터 간 의존성을 나타내는 a, b, s가 주어진다.

(a가 b를 의존한다는 의미. b가 해킹되면 s초 후에 a도 해킹된다는 의미.)

 

출력으로는 각 테스트케이스마다 총 해킹된 컴퓨터 수와 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력하면 된다.

---

문제 해결

이 문제는 다익스트라 알고리즘으로 풀 수 있다.

이 문제에서의 의존성 관계라는 것이 방향이 있는 edge를 의미한다.

우선순위 큐를 이용하여, 시간 복잡도 O(n log d)로 해결 가능하다.

 

다익스트라 알고리즘

distance 배열을 int(1e9)로 초기화한다.

우선순위 큐에 (0, 시작 컴퓨터)를 넣고 distance[시작 컴퓨터] 값을 0으로 update한다.

아래의 과정을 우선순위 큐가 빌 때까지 반복한다. 

우선순위 큐에서 dist와 node 값을 꺼낸다. 

만약 distance[node]의 값보다 dist가 크다면 update할 필요가 없기 때문에 넘어간다.

그렇지 않으면 node에 연결된 의존 관계를 확인한다. a는 node에서 갈 수 있는 컴퓨터. s는 가는데 걸리는 시간

만약 distance[a]가 dist + a보다 크다면 dist+a값으로 값을 update하고 (dist+a, a)를 우선순위 큐에 넣는다.

 

정답을 구하기 위해 distance 배열에서 int(1e9) 값이 아닌 것의 개수를 출력하고 그들 중 가장 큰 값을 출력한다. 

---

코드

import heapq
INF = int(1e9)
testcase = int(input())

def dijkstra(start):
    queue = []
    distance = [INF for _ in range(n+1)]

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

    while queue:
        dist, node = heapq.heappop(queue)
        if distance[node] < dist:
            continue
        for a, s in graph[node]:
            cost = dist + s
            if distance[a] > cost:
                distance[a] = cost
                heapq.heappush(queue, (cost, a))

    result = []
    for i in distance:
        if i != INF:
            result.append(i)
    print(len(result), max(result))
for _ in range(testcase):
    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))
    dijkstra(c)

---

결과

---