[백준] 10282번 : 해킹

문제

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

풀이

[백준] 10282 : 해킹 🥇(골드 4)
🎯 39.684%
⏰ 걸린 시간 : 48분
⏲ 시간복잡도
: 다익스트라 -> O(dlogn) : dn인데 우선순위 큐 사용해주면 탐색이 logn로 줄어든다.

• 알고리즘 유형 : [다익스트라]

✅ 문제 요약

0. 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다.
1. 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다.
2. 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.
3. yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

✅ 출력

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

✅ 풀이방법 & 다익스트라 알고리즘로 푼 이유?

✔️ 전형적인 최단 경로 문제이다.
0. 다익스트라 : 한 정점에서 모든 정점까지의 거리를 계산함
1. 가는 길을 택하는데 최소의 거리 길이를 택하여서 가야하기 때문이다.
2. 플로이드 워셜의 경우는 시간 복잡도가 O(V^3)인데 D의 입력이 10,000이기 때문에 2초를 초과 할 수 있다.

코드(code)

import sys
import heapq
input = sys.stdin.readline

tc = int(input())
#  n: 컴퓨터 개수 / d : 의존성 개수 / c: 해킹당한 컴퓨터 번호
#  a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨
def dijkstra(start, infection_times, graph):

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

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

        if infection_times[now] < time:
            continue
  
        for a, s in graph[now]:
            now_totalTime = time + s
            if now_totalTime < infection_times[a]:
                infection_times[a] = now_totalTime
                heapq.heappush(q,(now_totalTime,a))


for t in range(tc):
    INF = int(1e9)
    n, d, c = map(int,input().split())
    graph = [[] for _ in range(n+1)]
    infection_times = [INF] * (n+1)


    for i in range(d):
        a, b, s = map(int,input().split())
        graph[b].append((a,s))
    dijkstra(c, infection_times, graph)

    cnt,last_time   = 0, 0 # 감염된 컴퓨터 수, 최종 시간
    for i in range(1, n+1):
        if infection_times[i] != INF:
            cnt +=1
            last_time = max(last_time,infection_times[i])
    print(cnt, last_time)

회고

조금씩 이해가 되면서 풀린다.

• 가중치가 있는 최단거리를 찾는 알고리즘으로는 다익스트라가 적합하다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/Dijkstra/10282(%ED%95%B4%ED%82%B9).py