[Graph: Dijkstra] 743. Network Delay Time ★

743. Network Delay Time

 

이 문제는 그래프 문제로, **다익스트라 알고리즘(Dijkstra's Algorithm)**을 사용해서 해결할 수 있는 전형적인 단일 출발점 최단 경로 문제입니다. 아래에 차근차근 설명해드릴게요.

---

✅ 문제 요약

• 노드가 1부터 n까지 있고,
• times = [[u, v, w], ...] 형식으로 **방향성(edge)**과 **가중치(weight)**가 주어짐.
  • u에서 v로 가는 데 w 시간이 걸린다는 뜻.
• 시작 노드 k에서 신호를 보낼 때, 모든 노드가 신호를 받는 데 걸리는 시간 중 가장 오래 걸리는 시간을 구해야 함.
• 모든 노드가 도달 불가능하다면 -1을 리턴함.

Return the minimum time it takes for all the n nodes to receive the signal.

=> 모든 노드가 신호를 받는 데 걸리는 "최소한의 전체 시간"

=> 즉, 가장 늦게 도달한 노드의 도착 시간

 

import heapq
from typing import List

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = {}
        # You are given a network of n directed nodes, labeled from 1 to n. 
        # 문제에서는 노드 번호가 1부터 n까지임을 전제
        # range(n) 이 아니라, range(1, n+1)
        for i in range(1, n+1):
           adj[i] = []

        for src, dst, time in times:
            adj[src].append([time, dst])  # src에서 dst로 가는 데 time만큼 걸림

        shortest = {}  # 각 노드까지의 최단 거리를 저장

        # [0, k] 아니라, [[0, k]] 임 <-- 주의!!
        minheap = [[0, k]]  # 최소 힙에 (거리, 노드) 형태로 저장

        while minheap:
            w1, n1 = heapq.heappop(minheap)  # 가장 짧은 거리의 노드 선택
            if n1 in shortest:  # 이미 방문한 노드면 스킵
                continue

            shortest[n1] = w1  # n1까지의 최단 거리 확정

            for w2, n2 in adj[n1]:  # n1에서 갈 수 있는 이웃 노드들 순회
                if n2 not in shortest:
                    heapq.heappush(minheap, [w1+w2, n2]) # 인자 2개 넣어야!!

        # 모든 노드가 시그널 수신 못받으면 return -1
        maxTime = float("-inf")
        for i in range(1, n+1):
            if i not in shortest:
                return -1            # 어떤 노드라도 도달하지 못했다면 -1 반환
            maxTime = max(maxTime, shortest[i])  # 가장 오래 걸린 시간 저장

        # print(shortest)  # 디버깅용 출력
        return maxTime