743. Network Delay Time

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags	dijkstra
난이도
발행 여부
사이트	Leet code
실수 유형
이해
최종 편집 일시	@2021년 12월 10일 오후 10:53
푼 날짜	@2021년 12월 10일 오후 10:35

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드

풀이 코드 (책)

퇴고

문제 해설 및 주의사항

원문

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 비교 코드

  Bellman-Ford

  Time: O(VE)Space: O(N)

  class Solution:
      def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
          dist = [float("inf") for _ in range(N)]
          dist[K-1] = 0
          for _ in range(N-1):
              for u, v, w in times:
                  if dist[u-1] + w < dist[v-1]:
                      dist[v-1] = dist[u-1] + w
          return max(dist) if max(dist) < float("inf") else -1
  

  SPFA

  Time: average O(E), worst O(VE)Space: O(V+E)

  class Solution:
      def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
          dist = [float("inf") for _ in range(N)]
          K -= 1
          dist[K] = 0
          weight = collections.defaultdict(dict)
          for u, v, w in times:
              weight[u-1][v-1] = w
          queue = collections.deque([K])
          while queue:
              u = queue.popleft()
              for v in weight[u]:
                  if dist[u] + weight[u][v] < dist[v]:
                      dist[v] = dist[u] + weight[u][v]
                      queue.append(v)
          return max(dist) if max(dist) < float("inf") else -1
  

  Dijkstra

  Time: O(E+VlogV)Space: O(V+E)

  class Solution:
      def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
          weight = collections.defaultdict(dict)
          for u, v, w in times:
              weight[u][v] = w
          heap = [(0, K)]
          dist = {}
          while heap:
              time, u = heapq.heappop(heap)
              if u not in dist:
                  dist[u] = time
                  for v in weight[u]:
                      heapq.heappush(heap, (dist[u] + weight[u][v], v))
          return max(dist.values()) if len(dist) == N else -1
  

  Floyd-Warshall

  Time: O(V^3)Space: O(V^2)

  class Solution:
      def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
          dist = [[float("inf") for _ in range(N)] for _ in range(N)]
          for u, v, w in times:
              dist[u-1][v-1] = w
          for i in range(N):
              dist[i][i] = 0
          for k in range(N):
              for i in range(N):
                  for j in range(N):
                      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
          return max(dist[K-1]) if max(dist[K-1]) < float("inf") else -1