[알고리즘] Leetcode #743 네트워크 딜레이 타임 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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

 

Constraints

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

 

Code

def networkDelayTime(self, times, N, K):
    graph = collection.defaultdict(list) # 인접 리스트로 만들어주기
    # times = [[2, 1, 1], [2, 3, 1], [3, 4,1]], N = 4, K = 2
    for u, v, w in times:
        graph[u].append((v, w)) # 시작점 인덱스에 도착점, 정점 간 거리 append

    Q = [(0, K)] # (소요 시간, 정점) # 시작점
    dist = collection.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: # dist의 키 개수가 N(전체 노드 개수)과 동일한지
        return max(dist.values())
    return -1

 

이 문제에서는 다익스트라 알고리즘을 활용해 모든 노드가 신호를 받는데까지 걸리는 시간과 모든 노드가 신호를 받을 수 있는지를 판별해야 한다. 우선, 입력값으로 받은 time의 시작점, 도착점, 소요 시간을 graph라는 dictionary에 저장한 후 (defaultdict 사용), heapq 모듈을 사용해 최단 경로를 찾는다. 초기화 한 dist 딕셔너리에 node와 time을 하나씩 추가하며 (맨 처음은 시작점 2, 소요시간 0), graph에 할당한 정보들을 활용해 Q에 계속적으로 노드와 소요 .시간 정보를 추가한다. 마지막으로 문제의 조건에 의해 '모든 노드에 도달할 수 있는지' 에 대한 코드를 추가한다. 전체 노드의 개수 N과 dist의 길이가 같지 않으면 모든 노드를 돌 수 없는 것이므로 -1를 return한다.

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)