[파이썬 알고리즘 인터뷰][최단경로] 네트워크 딜레이 타임

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

출발지에서 각 노드까지 weight중 최대값 구하기, 못가는 노드가 있을 경우 -1

 

책에서 구현된 코드

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

 

기억해야할 기법

• 우선순위 큐에 첫 노드를 입력할 때
  
  • Q = [(0, k)]
• 방문 여부와 값을 모두 비교할 때
  • 방문 여부 : dict의 key 확인
  • 값 비교 : dict의 value 확인

 

내가 구현한 코드

from collections import defaultdict
import heapq, sys

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    dic = defaultdict(list)
    weight = [sys.maxsize for _ in range(n)]
    weight[k-1] = -1
    visited = [False for _ in range(n)]
    q = []

    for u, v, w in times:
        dic[u-1].append((w, v-1))

    for row in dic[k-1]:
        heapq.heappush(q, row)

    while len(q):
        w, v = heapq.heappop(q)
        if w < weight[v]:
            weight[v] = w
            visited[v] = True
            for nxt_w, nxt_v in dic[v]:
                if not visited[nxt_v]:
                    heapq.heappush(q, (nxt_w+w, nxt_v))

    if max(weight) < sys.maxsize:
        return max(weight)
    return -1

• 내가 구현한 알고리즘이 약간 더 빠름
  - 아무래도 책에서 구현한 알고리즘의 마지막에 dist의 values로 인해 생긴 copy 때문인듯