[백준][Python] 10282번: 해킹 (265)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

10282번: 해킹

 

생각의 흐름

이번 문제는 다익스트라를 알면 금방 해결할 수 있는 문제이다.

 

문제는 다익스트라인 것을 어떤 부분에서 눈치챌 수 있을까?

 

사실 문제만 읽으면 최단경로를 구해야 한다는 점이 명확하게 보이지 않을 수 있다(적어도 나는 그랬다)

일단 그레프를 순회 해야 겠다 정도만 느껴진다.

다른 블로그들 대부분을 봐도 왜 다익스트라인지는 말하지 않고 있다...

 

내가 다익스트라 라고 느낌 지점은 다음과 같다. 우선 다음 그림을 살펴보자.

1번 지점에서 3번 지점까지 한번에 가면 10초가 걸린다.

하지만, 2번을 거처서 지나가면 총 5초가 걸린다. 5초가 더 빠르기 때문에 3번 컴퓨터는 (1 -> 2 -> 3) 경로를 통해 감염된다.

즉, 더 빠른 경로를 통해서 감염이 진행되게 된다.

 

따라서 최단비용을 기준으로 경로를 찾아야 하며, 다익스트라를 적용하게 되는 것 이다!

 

나의 코드

import sys
import heapq

C = int(sys.stdin.readline())
adj = list
INF = 987654321


def dijkstra(start: int, dist: list):
    hq = []
    heapq.heappush(hq, (0, start))
    dist[start] = 0

    while hq:
        now_cost, now_v = heapq.heappop(hq)

        if dist[now_v] < now_cost:
            continue

        for next_v, next_cost in adj[now_v]:
            if dist[next_v] > dist[now_v] + next_cost:
                dist[next_v] = dist[now_v] + next_cost
                heapq.heappush(hq, (dist[next_v], next_v))


for _ in range(C):
    n, d, c = map(int, sys.stdin.readline().split())

    adj = [[] for _ in range(n + 1)]
    dist = [INF for _ in range(n + 1)]
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        adj[b].append((a, s))

    dijkstra(c, dist)

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

    print(f"{cnt} {ans}")