[LeetCode/Python] 743. 네트워크 딜레이 타임(Network Delay Time) (feat.다익스트라 알고리즘)

다익스트라

 

K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라.

 

불가능할 경우 -1을 리턴한다.

 

입력값 (u, v, w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

 

example:

 

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

 

Output: 2

 

 

 

 

** 깔끔한 풀이

 

1. 다익스트라 알고리즘 구현

 

 

class Solution:
    def networkDelayTime(self, times, 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

 

해설:

 

다익스트라 알고리즘을 우선 이해해야 한다.

 

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

C++로 되어있긴 한데 개념을 잡는데는 부족함이 없다.

 

우선순위 큐로 구현하여 시간 복잡도를 낮출 수 있다.

 

우선순위 큐를 사용하지 않는다면 dist 값을 모든 경로마다 경신해야 돼서 오래 걸림;;

 

Q를 heapq로 구현하여 최소 힙을 빼서 dist를 구해나간다.

 

만약 dist에 node가 이미 존재한다면

 

dist에 들어있는 것이 최소 시간이므로 건들지 말고 넘어간다.

 

이렇게 dist를 구하고 나면 문제 특성상 dist에 모든 정점의 소요 시간이 들어있어야 하므로

 

len(dist) == n으로 확인을 해주고

 

그 후 최댓값을 리턴해주자.

 

 

 

 

 

 

2. 내가 직접 짠 코드

 

 

class Solution:
    def networkDelayTime(self, times, n: int, k: int) -> int:
        grid = [[sys.maxsize] * n for _ in range(n)]
        for time in times:
            grid[time[0] - 1][time[1] - 1] = time[2]
        for i in range(n):
            grid[i][i] = 0
        # k에서 출발
        ver_time = grid[k - 1].copy()
        # 각 정점을 지나면서 소요 시간 계산
        visited = [k - 1]
        for _ in range(n - 1):
            # 가장 최소 거리를 갖는 정점 반환
            min = sys.maxsize
            index = sys.maxsize
            for i in range(n):
                if ver_time[i] < min and i not in visited:
                    min = ver_time[i]
                    index = i
            if index == sys.maxsize:
                return -1
            visited.append(index)
            for i in range(n):
                if ver_time[i] > ver_time[index] + grid[index][i] and index != i:
                    ver_time[i] = ver_time[index] + grid[index][i]
        return max(ver_time)

 

해설:

 

나름대로 우선순위 큐를 사용하지 않고 다익스트라 알고리즘을 이용하여 풀어봤다.

 

이 문제만 그런건진 모르겠는데 시간 복잡도 또한 1번 코드랑 다를 바가 없었다..!

 

grid에 노드 간 소요시간을 넣어줬고

 

k에서 출발하여 소요 시간이 적은 곳부터 이동하면서 소요 시간을 갱신해주었다.