문제 해설 및 주의사항

원문

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 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.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

번역 및 주의사항

• 아래 그림과 같은 그래프가 주어진다.

  • times : 노드에서 노드로 움직일 때 걸리는 시간이 표시된다.
    • (u, v, w) : (출발지, 도착지, 걸리는 시간)
    • k : 시작점
    • n : 노드의 개수
  • 모든 n 개의 노드를 방문하는데 걸리는 시간을 return 하라.
  • 모두 방문할 수 없다면 -1 을 return

  

풀이

1. 모든 노드에 도달할 수 있는지 여부
2. 모든 노드가 신호를 받는데 걸리는 시간

총 두 개를 판별해야 한다.

• 이를 위해, 다익스트라 알고리즘을 이용해보자.
  • bfs 를 이용한다.
  • 가중치가 음수인 경우는 처리할 수 없다.
    • 음수 가중치라면 벨만-포드 알고리즘을 이용하자
  • 우선순위 큐 heapq 를 이용하여 시간 복잡도를 줄일 수 있다.

내 풀이 코드

py

풀이 코드 (책)

class Solution:
    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)]
        
        # node 까지의 최단 거리를 저장함
        dist = collections.defaultdict(int)
        
        while Q :
            current_time, current_node = heapq.heappop(Q)
            
            if current_node not in dist:
                dist[current_node] = current_time
                # 현재 node 까지의 최단 거리를 구했으므로, 여기서 인접한 node를 방문함
                for v, w in graph[current_node]:
                    heapq.heappush(Q, (current_time + w, v))
        
        return max(dist.values()) if len(dist) == n else -1

퇴고

• 벨만-포드 / 다익스트라 / spfa 비교 코드