[리트코드] Network Delay Time(python)

리트코드, Network Delay Time_네트워크 지연 시간

TL;DR

• 너비 우선 탐색(BFS)
• 다익스트라 알고리즘(Dijkstra Algorithm)

문제 요약

1. 1부터 n까지 노드가 있는 네트워크가 주어진다. 주어진 네트워크는 출발 노드, 도착 노드, 출발 노드로부터 도착 노드까지 걸리는 시간을 의미한다.
2. 주어진 k 노드로부터 신호를 전달한다고 했을 때 모든 n개의 노드들 도는데 걸리는 시간을 반환하라.
3. 만약 모든 노드를 순회할 수 없다면 -1을 반환하라.

 

- 주어진 k 노드로부터 그래프에 존재하는 모든 노드를 순회할 때의 시간을 반환하면 된다. 이는 가장 k 노드로부터 가장 먼 거리의 노드까지 걸리는 시간을 반환하면 된다.

- 모든 노드를 순회할 수 있다면 BFS에서 조회할 수 있는 경로의 수가 노드의 수와 같아야 한다. 만약 가능한 경로의 수와 노드의 수가 일치하지 않을 경우, -1을 반환하면 된다.

입출력 형태

입출력 예시

 

- 예시 1번의 경우, 주어진 입력을 그래프로 나타내면 그림과 같이 된다. 이 때, 시작 노드 2로부터 가장 먼 노드 4까지 걸리는 시간은 총 2가 걸린다. 따라서 정답이 2가된다.

- 예시 2번의 경우, 1번 노드에서 2번 노드로 가는 경로는 존재하지만 2번 노드로부터 1번 노드까지 갈 수 있는 경로는 존재하지 않는다. 따라서 이 때는 -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)]
        distances = collections.defaultdict(int)
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in distances:
                distances[node] = time
                for v, w in graph[node]:
                    tmp = time + w
                    heapq.heappush(Q, (tmp, v))
                    
        if len(distances) == n:
            return max(distances.values())
        
        return -1

 

최단 경로 찾기 중 하나로 다익스트라 알고리즘을 BFS로 구현하면 된다. python에서는 `heapq`를 사용하면 구현할 수 있다.

- 우선 입력받은 `times`로부터 그래프를 구성한다. 이 때, 단방향 그래프를 도착 노드와 가중치를 담도록 저장한다.

- Q는 노드까지 걸리는 시간 정보를 담는다. distances는 각 노드까지 걸리는 시간을 dictionary 형태로 저장한다.

- 큐를 순회하며 각 노드에 방문하지 않았다면 노드에 대한 시간을 갱신한다.

  - 각 노드로부터 갈 수 있는 경로를 조회하며 큐에 삽입한다.

  - heapq에 의해서 heap 구조를 유지하도록 경로를 삽입한다.

- 모든 노드를 순회하였다면 distances의 길이가 노드의 개수인 n과 같아야 한다.

  - 모든 노드를 순회할 수 있다면 가장 오래 걸리는 시간을 반환한다.

  - 그렇지 않은 경우는 모든 노드를 순회할 수 없는 경우이므로 -1을 반환한다.