[최단 경로 문제] 네트워크 딜레이 타임

743 | Network Delay Time
https://leetcode.com/problems/network-delay-time/

 

 

 

작성 코드

 

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        def bfs(time, visited_net, next_net):
            visit = visited_net[-1]
            if not next_net[visit] or len(visited_net) == n:
                times.append(time - sum(times))
                return
            for e, w in next_net[visit]:
                if e not in visited_net:
                    next_net_temp = copy.deepcopy(net)
                    next_net_temp[visit].remove([e, w])
                    visited_net.append(e)
                    time += w
                    bfs(time, visited_net, next_net_temp)
            return


        net = collections.defaultdict(list)
        for start, end, weight in times:
            net[start].append([end, weight])
        times = []
        bfs(0, [k], net)
        return(-1 if not max(times) else max(times))

 

• 방문한 net - visited_net / 방문해야 할 net - next_net
• 대부분의 test case를 통과하지 못 함
• 경로가 여러 개로 나뉘고 합쳐졌을 때(한 지점에 도착하는 방법이 여러 개일 때)를 해결하지 못 함

 

 

이상 코드

 

다익스트라 알고리즘 구현

 

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

 

• Q는 (소요시간, 정점) 구조
• Q는 우선순위 큐이므로 값이 계속 쌓이다가 낮은 값부터 하나씩 추출되면서 제거
• dist는 항상 최솟값부터 세팅, 이미 값이 존재한다면 최단 경로가 아니라는 것

 

 

핵심

 

• heapq 구조를 익힐 필요가 있음