[알고리즘][최단 거리] - 1. 네트워크 딜레이 타임

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/network-delay-time/

k부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값(u,v,w)는 각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

---

[다익스트라 알고리즘 구현]

import collections
import heapq


class Solution(object):
    def networkDelayTime(self, times, n, k):
        graph = collections.defaultdict(list)

        #그래프 인접 리스트 구성
        for u,v,w in times:
            # u -> v로 가는 비용이 w라는 의미
            graph[u].append((v,w))

        #큐 변수: [(소요 시간, 정점)]
        q = [(0,k)]

        #거리 비교를 위한 변수
        distant = collections.defaultdict(int)

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

            if node not in distant:
                distant[node] = time
                for v, w in graph[node]:
                    alt = time + w
                    heapq.heappush(q(alt, v))
        if len(distant) == n:
            return max(distant.values())
        return -1