[BOJ] 10282번 해킹 / 사용언어 : 파이썬(python)

※ 문제링크

10282번: 해킹

해당문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 입력받은 값들로 그래프를 구현하고 다익스트라로 최단거리를 구해준 후 이어져 있는 컴퓨터의 수와 최대 시간만 출력해주면 되었기에 생각보다 쉽게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들과 2차원 리스트를 활용하여 그래프를 구현해준다.

2. 각각의 컴퓨터들로 갈 수 있는 최단시간을 구하기 위한 다익스트라 함수를 작성해준다.

3. 입력받은 값들로 결과값을 출력해준다.

 

import sys
from heapq import heappush, heappop

def dijkstra(start):
    heap = []
    dp = [float('inf') for _ in range(n+1)]
    dp[start] = 0
    heappush(heap, [0 ,start])

    while heap:
        t, n_c = heappop(heap)
        for n_c_t, n_n_c in graph[n_c]:
            n_t = t + n_c_t
            if n_t < dp[n_n_c]:
                dp[n_n_c] = n_t
                heappush(heap, [n_t, n_n_c])
    check = dp.count(float('inf')) - 1
    ans1 = n - check
    ans2 = sorted(dp)[-check-2]
    return ans1, ans2
    
# input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n, d, c = map(int, input().split()) # n: 컴퓨터의 수 / d: 의존성의 개수 / c: 해킹된 컴퓨터
    graph = [[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        graph[b].append([s, a])

    print(*dijkstra(c))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.