<aside> 🔥 리트코드 743번 문제 링크

</aside>

<aside> 🔥 문제 정리

k부터 출발해 모든 노드가 신호를 받을 수 있는지 구하는 문제

불가능하면 -1을 리턴한다.

입력값 n : 노드의 개수

입력값 u, v, w 는 출발지 도착지 소요 시간으로 구성된다.

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

</aside>

<aside> 🔥 접근 방법

문제가 처음에는 다소 이해가 안갔는데 간단하게 생각하면 단방향으로 연결되어있는 간선에서

시작지점 k에서 시작할 때 갈 수있는 간선이 없으면 -1을 출력하고, 나머지는 다익스트라 최단거리를

구해서 최대값을 반환하면 될거 같다.

</aside>

<aside> 🔥 코드

기본적인 다익스트라 알고리즘을 활용했다.

다른 점은 아래 코드인데 만약 간선이 없어 갈곳이 없으면 거리 테이블은 무한으로 지정되어있을 것이다.

따라서 합계가 무한대이상이면 -1을 출력하고 아니면 가장 먼곳까지 도달하는 시간을 출력한다.

result = dist[1:]
            if sum(result) >= INF:
                return -1
            else:
                return max(result)

아래 나머지 코드는 기본적인 힙을 이용한 다익스트라 알고리즘이다.

class Solution:
    def networkDelayTime(self, times, n, k):
        INF = int(1e9)
        graph = [[] for _ in range(n + 1)]
        for time in times:
            a, b, c = time
            graph[a].append((b, c))
        
        def dijkstra_pq(graph, start):
            N = len(graph)
            dist = [INF] * N

            q = []
            heapq.heappush(q, (0, start))
            dist[start] = 0
            while q:
                acc, cur = heapq.heappop(q)

                if dist[cur] < acc:
                    continue

                for adj, d in graph[cur]:
                    cost = acc + d

                    if cost < dist[adj]:
                        dist[adj] = cost
                        heapq.heappush(q, (cost, adj))
            
            result = dist[1:]

</aside>