[BOJ/Python] 10282_해킹

문제 출처:https://www.acmicpc.net/problem/10282

10282번: 해킹

문제

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 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)가 두 번 이상 존재하지 않는다.

출력

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

예제 입력 1

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4

예제 출력 1

2 5
3 6

---

풀이

 

다익스트라 알고리즘을 이용하여 문제를 풀었다.

코드는 다음과 같다.

 

import sys
import heapq
 
INF = int(1e9)
 
def dijkstra(start,distance,graph):
    queue = []
    heapq.heappush(queue,(0,start))
    distance[start] = 0
 
    while queue:
        dist,node = heapq.heappop(queue)
 
        if distance[node] < dist:
            continue
 
        for next in graph[node]:
            cost = dist + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(queue,(cost,next[0]))
    return distance
 
 
t = int(sys.stdin.readline())
 
for _ in range(t):
    n,d,c = map(int,sys.stdin.readline().split())
    distance = [INF for _ in range(n+1)]
    graph = [[] for _ in range(n+1)]
    for _ in range(d):
        a,b,s = map(int,sys.stdin.readline().split())
        graph[b].append((a,s))
 
    distance = dijkstra(c,distance,graph)
    
    count = 0
    max_distance = 0
    for i in distance:
        if i!=INF:
            count+=1
            if i>max_distance:
                max_distance=i
    
    print(count, max_distance)

 

1. 우선 테스트 케이스의 개수 t를 입력받고, t만큼 수행한다.
2. 우선 n개의 노드의 distance를 모두 INF(무한대)로 초기화 하고, 각 노드의 간선 정보를 입력받아 graph에 저장한다.
3. dijkstra 함수 부분은 다음과 같다.
4. 우선 최소힙을 이용하여 우선순위 큐로 구현한다.
5. 출발지 노드의 번호를 입력받아 큐에 넣어주고, 출발지에서 출발지 까지의 거리는 0이므로 0으로 초기화한다.
6. 큐에 원소가 존재하는 동안 반복한다.
7. 큐에 원소가 더이상 존재하지 않으면 함수를 종료한다.
8. dijkstra함수를 호출하고 나면, 출발지 노드와 연결되어 있는 (다른 노드를 거쳐서 연결되어 있는 경우 포함) 모든 노드를 탐색하였으므로 distance 리스트에는 출발지로부터 각 노드들까지의 거리 정보가 들어있다.
9. 여기서 어떠한 노드의 거리가 INF라면, 출발지노드와 연결되어있지 않음을 의미한다.
10. 이 문제에서 출발지 노드는 감염된 컴퓨터이고, 출발지 노드로부터 연결되어있는 노드들은 전부 감염이 되므로, distance 리스트에서 값이 INF가 아닌 경우는 모두 감염된 컴퓨터임을 알 수 있다.
11. 따라서 INF가 아닌 값을 갖고 있는 노드의 개수가 감염된 컴퓨터의 수이다.
12. 또한, 감염된 컴퓨터들 중 거리의 값이 제일 큰 경우가 마지막 컴퓨터가 감염된 시간임을 알 수 있다.