743. Network Delay Time | py풀이

1. 문제

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

Network Delay Time - LeetCode

 

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

 

 

하나의 네트워크에 n개의 노드가 있고, 간선 정보 times가 주어진다.

times[i] = (u, v, w)

 

• u → v 로 가는 데 걸리는 시간은 w
• 시작 노드 k에서 신호를 보냈을 때
• 모든 노드가 신호를 받는 최소 시간을 구하는 문제
• 도달 불가능한 노드가 있다면 -1 반환

 

2. 풀이

이 문제는 다음 조건을 만족한다:

• 방향 그래프
• 가중치 존재
• 단일 시작점
• 최단 거리 문제

따라서 다익스트라(Dijkstra) 알고리즘을 사용하면 된다.

 

우리가 구해야 하는 것은 시작점 k에서 각 노드까지의 최단 거리 그 중 가장 큰 값

 

코드 설계:

1. 그래프 생성
2. 다익스트라 수행
3. 모든 노드 방문 여부 확인
4. 최단 거리 중 최대값 반환

구현 코드:

import heapq
from collections import defaultdict

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

        # 1. 그래프 생성
        graph = defaultdict(list)
        for time in times:
            graph[time[0]].append((time[2], time[1]))
        
        # 2. 다익스트라 알고리즘
        costs = {}
        pq = []
        heapq.heappush(pq, (0, k))

        while pq: 
            cur_cost, cur_node = heapq.heappop(pq)

            # 이미 방문한 노드는 건너뜀
            if cur_node not in costs:
                costs[cur_node] = cur_cost

                for next_cost, next_node in graph[cur_node]:
                    next_cost = cur_cost + next_cost
                    heapq.heappush(pq, (next_cost, next_node))

        # 3. 방문 못한 노드 확인
        if len(costs) != n:
            return -1

        # 4. 최소값 중 최대값 리턴
        return max(costs.values())