[백준] 파이썬 10282번 : 해킹

 

 

# 다익스트라 
# a가 b에 의존함 => b에서 a로 갈 수 있다 

from heapq import *
import sys
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()) # 컴퓨터a, 컴퓨터b, 감염되는데 걸리는 시간
        graph[b].append([a, s]) # 의존하는 쪽으로 갈수있으니 b에 추가
    time = [1e9] * (n + 1) # 시간을 최대값으로 초기화
    heap = [] # 힙
    time[c] = 0 # 시작점은 0으로 초기화
    heappush(heap, [0, c]) # 거리(0), 시작점을 힙에 추가

    while heap: # 힙이 빌때까지 반복
        cur_time, cur_node = heappop(heap) # 현재 소요된 시간, 노드
        if time[cur_node] < cur_time: # 만약 현재 소요된 시간이 더 크다면 이미 최솟값임으로 변경할 필요 없음
            continue
        for next_node, next_time in graph[cur_node]: # 현재 노드에서 갈수있는곳 탐색
            if time[next_node] > cur_time + next_time: # 기존 소요시간보다 현재+다음 시간이 더 적다면
                time[next_node] = cur_time + next_time # 값 갱신
                heappush(heap, [cur_time + next_time, next_node]) # 탐색 위해 힙에 추가
    
    cnt = 0 # 감염된 컴퓨터 개수
    result = 0 # 마지막 컴퓨터 감염되는데 걸리는 시간
    for i in time:
        if i != 1e9: # 초기화된 값이 아니라면
            cnt += 1 # 컴퓨터 개수 증가
            result = max(result, i) # 소요시간 중 최대값을 찾음
    
    print(cnt, result)

 

개념을 어려워했었던 다익스트라 문제! 그래도 같은 유형의 문제를 풀어보니 조금씩 감을 잡게 되었다. 

이 문제에서 중요한건 의존성에 따라 간선의 방향이 정해지는 것이다. 

문제를 보면 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.는 내용이 있다.

정리하면, a는 b에 의존하지만 b는 a에 의존하지 않을경우, b는 a에 갈 수 있지만 a는 b로 갈 수 없다. 즉 의존하는 컴퓨터가 있다면 그 컴퓨터의 접근을 허용한다는 의미였다. 

 

이 이후로는 간단했다. 그래프와 비용을 의미하는 시간을 초기화해주고 힙을 선언해준 다음 출발지점과 거리를 넣어준다. 그리고 힙이 빌때까지 반복하고 최소값이 나오면 값을 갱신해주고 힙에 추가해준다. 

반복문이 끝나면 출력해줄 감염된 컴퓨터 개수와 마지막 컴퓨터가 감염되기까지 걸리는 시간을 찾아야한다. 

배열 time을 반복하며 초기화 된 값이 아닌지 확인해 감염된 컴퓨터를 추가하고, 소요시간 중 최대값을 찾아 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력해준다.

 

 

 

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

10282번: 해킹