40. Network Delay Time

리트코드

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

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

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

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

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
        

• 이 문제에서는 다음과 같은 2가지 사항을 반별해야 한다.

  1) 모든 노드가 신호를 받는 데 걸리는 시간

  • 가장 오래 걸리는 노드까지의 시간

    • 즉, 가장 오래 걸리는 노드까지의 최단 시간

  • 이는 다익스트라 알고리즘으로 추출할 수 있다.

  2) 모든 노드에 도달할 수 있는지 여부

  • 이는 모든 노드의 다익스트라 알고리즘 계산 값이 존재하는지 유무로 판별할 수 있다.

  • 만약 노드가 8개인데 다익스트라 알고리즘 계산은 7개 밖에 할 수 없다면, 나머지 한 노드에는 도달할 수 없다는 의미이다.

    • 이 경우 모든 노드에 도달할 수 없는 경우이므로 -1을 리턴한다.

• 파이썬에서 우선순위 큐를 최소 힙(Min Heap)으로 구현한 모듈인 heapq를 사용하는 형태로 구현해본다.

<우선순위 큐를 이용한 다익스트라 알고리즘 수도코드>

function Dijkstra(Graph, source):
    dist[source] <- 0
    
    create vertex priority queue Q
    
    for each vertex v in Graph:
        if v ≠ source
            dist[v] <- INFINITY
            prev[v] <- UNDEFINED
            
         Q.add_with_priority(v, dist[v])
         
     while Q is not empty:
         u <- Q.extract_min()
         for each neighbor v of u:
             alt <- dist[u] + length(u, v)
             if alt < dist[v]
                 dist[v] <- alt
                 prev[v] <- u
                 Q.decrease_priority(v, alt)
                 
      return dist, prev

• 그래프에서 각 정점과 거리를 우선순위 큐에 삽입하는 부분 Q.add_with_priority(v, dist[v]), 그리고 우선순위 큐에서 최소 값 추출 u <- Q.extract_min()을 통해서 이웃을 살펴보는 for each neighbor v of u: 수도코드를 확인할 수 있다.

• 실행 가능한 파이썬 코드로 구현해보자.

• 그래프부터 구성한다.

  • 위키피디아 수도코드는 이미 그래프가 구성된 상태라 가정하고 입력값을 받았지만, 이 문제에서 입력값은 (u, v, w) 아이템 목록으로 구성된 리스트 형태며, 이를 키/값 구조로 조회할 수 있는 그래프 구조 (파이썬에서는 딕셔너리로 구현하는 인접 리스트)는 아니다.

  • 따라서 먼저 그래프를 인접 리스트로 표현하는 딕셔너리부터 만들어준다.

  • 딕셔너리 생성을 쉽게하기 위해 collections.defaultdict를 활용한다.

• 다음은 우선순위 큐를 위한 큐 변수를 정의한다.

  • 큐 변수 Q는 '(소요시간, 정점)` 구조로 구성한다.

    • 즉 시작점에서 '정점'까지의 소요 시간을 담아둘 것이다.

  • 초깃값은 시작점 K부터이므로, 소요 시간은 0이고, 따라서 (0, K)가 된다.

  • 거리를 의미하는 dist 변수는 아직 아무것도 셋팅하지 않는다.

• 수도코드에는 큐에 add_with_priority(), decrease_priority(), extract_min() 3번의 연산을 내리도록 구현되어 있다.

  • 여기서 decrease_priority()가 문제다.

  • 이 연산은 수도코드에서 우선순위를 조정하라는 의미로 쓰였는데, 우리가 사용하는 heapq 모듈은 우선순위 업데이트를 지원하지 않기 때문이다.

    • 우선순위를 업데이트하려면 먼저 해당되는 키를 찾아야하고 이는 결국 O(n) 시간 복잡도가 필요한 일로, heapq 모듈은 이 기능을 지원하지 않는다.

  • 여기서는 decrease_priority()가 필요 없도록 알고리즘을 살짝 변경해 구현해본다.

  
  

• 큐 순회를 시작하자마자 최솟값을 추출하는 건 수도코드와 동일하다. 그러나 바로 for each 구문으로 이웃 노드를 순회했던 수도코드와 달리, 그 작업은 잠시 뒤에 진행하고, 먼저 dist에 node의 포함 여부부터 체크한다.

  • 수도코드는 dist를 이미 무한대 값으로 채우고 시작했지만, 우리는 dist에 아무 값도 셋팅하지 않았기 때문에 처음에는 이 값이 비어있을 것이고, 이 경우에만 힙에 푸시(Push)하는 형태로 조금 다르게 구현할 것이다.

    • 이렇게 하면 큐의 우선순위를 업데이트할 필요 없이 존재 유무로만 진행할 수 있으며, dist에는 항상 최솟값이 셋팅될 것이다.

<최단 경로를 찾아 나가는 과정 도식화>

입력값 [[3,1,5], [3,2,2], [2,1,2], [3,4,1], [4,5,1], [5,6,1], [6,7,1], [7,8,1], [8,1,1]]

여기서 N = 8이고 K = 3이다.

• 1)은 입력값을 그래프로 표현한 것이다.

  • 시작점인 3을 중심으로 세 방향으로 뻗어나가는 구조다.

• 2)의 Q와 dist는 위에서부터 차례로, 변수에 삽입되는 순서대로 값을 나열했다.

  • 여기서 Q는 우선순위 큐이므로 값이 계속 쌓이다가 낮은 값부터 하나씩 추출되면서(최소 힙이다) 제거된다.

  • dist에 존재하지 않는다면 바로 dist의 값으로 time과 node의 순서가 바뀌면서 입력된다.

  • 이미 dist에 키가 존재한다면 그 값은 버리게 된다.

    • dist에는 항상 최솟값부터 셋팅되기 때문에 이미 값이 존재한다면 그 값은 더 오래 걸리는 경로이기 때문이다. 따라서 이 값은 버리게 된다

  • 그림의 2)에서는 [5,1], [6,1] 두 값이 버려지게 된다.

• 실제로 노드 1은 3->2->1 순서로 방문하면 소요 시간 4에 도달할 수 있으며, 이후에 삽입되려고 하는 5와 6은 모두 이보다 더 오래 걸리므로 모두 버린다.

  • 가장 먼저 입력되었던 경로가 최단 경로이며, 이후에 삽입되는 경로는 이보다 오래걸린다.

• 마지막으로 모든 노드에 도달할 수 있는지 여부를 판별한다.

  • dist 딕셔너리의 키 개수가 N과 동일한지 체크한다.

    • 전체 노드 개수만큼이 모두 dist에 있다면 모든 노드의 최단 경로를 구했다는 의미이고, 이는 모두 시작점에 도달이 가능하다는 의미이기도 하다.

    • 만약 노드 개수가 하나라도 모자란다면 그 노드는 시작점에서 도달할 수 없다는 뜻이며, 앞서 2가지 판별 조건 중 두 번째 조건을 만족할 수 없기 때문에 -1을 리턴한다.

      • 모든 노드가 신호를 받을 수 없기 때문