[leetcode] network delay time

network delay time

• n개의 노드가 존재하는 네트워크 (1 ~ n)
• times 는 (출발노드, 도착노드, 걸리는시간) 으로 구성된 리스트
• k노드에서 출발해서 다른 모든 노드가 신호를 받는데 걸리는 최소시간 구하기
• 1 <= len(times) <= 6000
• 1 <= k <= n <= 100
• (출발노드,도착노드,걸리는시간)에서 출발노드-도착노드 pair는 항상 unique

Solution

• times 리스트를 graph로 나타내기(연결리스트로 표현)
• 거리 테이블 초기화 INF 출발 노드만 0으로
• 우선순위큐는 출발노드, 출발노드 까지의 거리=0 으로 초기화
• 다익스트라 알고리즘으로 출발점에서의 최단거리 찾기
• 최단 거리 테이블의 최대값 이 INF 이면 -1 반환 아니면 최대값 반환

Code

import heapq
from collections import defaultdict

class Solution(object):
    def networkDelayTime(self, times, n, k):

        INF = int(1e9)
        graph = defaultdict(list)

        for a, b, weight in times:
            graph[a].append((weight, b))

        dists = {i: INF for i in range(1, n + 1)}
        dists[k] = 0
        q = [(0, k)]

        while q:
            dist, v = heapq.heappop(q)
            if dist > dists[v]: continue
            for weight, w in graph[v]:
                if dists[w] > dist + weight:
                    dists[w] = dist + weight
                    heapq.heappush(q, (dists[w], w))

        result = max(dists.values())
        return result if result != INF else -1

Solution2

• INF 값 정의하지 않고 구현
• 최단거리가 결정된 노드만 dists에 삽입

Code2

import heapq
from collections import defaultdict

class Solution(object):
    def networkDelayTime(self, times, n, k):

        graph = defaultdict(list)
        dists = defaultdict(int)

        for a, b, weight in times:
            graph[a].append((weight, b))

        q = [(0, k)]

        while q:
            dist, v = heapq.heappop(q)
            if v not in dists:
                dists[v] = dist  
                for weight, w in graph[v]:
                    heapq.heappush(q, (dist + weight, w))

        return max(dists.values()) if len(dists)==n else -1