greentea31's Note

https://leetcode.com/problems/network-delay-time/

풀이 과정

노드와 간선이 주어질 때, 노드 k에서 시작해서 모든 노드를 순회하는데 걸리는 최소 시간을 구하는 문제이다. 순회가 불가능하면 -1을 출력해야 한다.

그래프에서 최소 거리, 최소 시간 문제를 풀 때는 BFS, 다익스트라, 플로이드, 벨만포드 알고리즘을 떠올릴 필요가 있고 이 문제에서는 간선의 가중치가 음수가 아님이 보장되므로 다익스트라를 통해서 문제를 해결하면 된다.

시작점 K와 나머지 모든 점의 최소 거리를 구하고, 거리의 최대값이 모든 점을 방문하는데 걸리는 시간이므로 이를 출력해주면 된다.

모든 정점으로의 거리가 추가되었는지 확인하고, 추가되지 않은 정점이 있으면 모든 정점을 순회하는게 불가능하다는 의미이므로 -1을 리턴해주면 된다.

소스 코드

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        dist = collections.defaultdict(int)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1