1 minute read

743. Network Delay Time

문제 링크

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

문제 설명

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.

제한 사항

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

입출력 예 #1

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

입출력 예 #2

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

입출력 예 #3

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

문제 풀이

bfs 기법을 이용하여 모든 노드를 순회하고, 최소 힙을 이용하여 어떤 노드를 갈 수 있는 방법들 중 시간이 가장 적게 걸리는 방법만 저장

  1. 모든 노드가 신호를 받는데 걸리는 시간 -> 최소 힙을 이용하여 어떤 노드를 갈 수 있는 시간들 중 최소값만 저장
  2. 모든 노드에 도달할 수 있는지 여부 -> 노드 총 합과 탐색한 노드의 개수가 동일한 지 확인
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)]
        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

Comments

You May Also Enjoy