[python/leetcode]network delay time/dijkstra/heapq

💬 문제

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.

 

Network Delay Time - LeetCode

 

 

🔅 아이디어

모든 노드가 신호를 받을 수 있는 시간을 계산해야 하니, 기본적으로 최단 경로 알고리즘을 사용한다(Dijkstra, BFS).

 

불가능할 경우 -1을 리턴해야 하기 때문에

 

1. 모든 경로에 도달할 수 있는가

2. 각 노드가 신호를 받는데 걸리는 시간

 

두개를 구하면 된다.

 

다익스트라 알고리즘을 사용하는 문제를 풀려고 하니 갑자기 슬로우 로드가 생각나서 처음으로 일상 글을 썼다. 

느리게 가는 내비게이션

Network delay time 문제는 얼마전에 프로그래머스에서 푼 배달 문제와 거의 똑같은 논리로 풀린다. 처음에 graph 원소들 넣어주는 부분을 제외하고는 다른 부분도 없는 것 같다..

 

[파이썬/프로그래머스]배달/다익스트라/우선순위큐

 

💬 코드

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))
        
        # 출발 시점에서 우리는 0시간을 소요했고, k에 위치해있다
        pq = [(0, k)]
        dist = collections.defaultdict(list)
        while pq:
            t, node = heapq.heappop(pq)
            # 방문 안했으면
            if node not in dist:
                # node에 가는데는 t 시간이 걸린다
                dist[node] = t
                for v, w in graph[node]:
                    # 이제 node랑 이어져있는 곳(도착지)에 간다
                    for v, w in graph[node]:
                        if v not in dist:
                            heapq.heappush(pq, (t+w, v))
        # n은 전체 노드의 개수니까, 전체 노드를 방문하는데 걸리는 시간을
        # 모두 구했다면 제일 마지막에 도착한 곳의 값을 리턴해준다
        return max(dist.values()) if len(dist) == n else -1
                
            

 

처음 풀었을 때 통과되긴 했는데 너무 느려서 확인을 해보니 가지치기(프루닝)를 안해줘서 그런거였다. 이미 거리를 구한 노드를 제외하고 방문하도록 수정하니 Runtime과 Memory가 모두 절반으로 줄었다.

 

DFS는 정말 가지치기를 안해주면... 안되는거같다.. 계속 머리에 새기고 있어야겠다.