[leetcode 2024/02/26] 743. Network Delay Time

https://leetcode.com/problems/network-delay-time/description/

Network Delay Time - LeetCode

 

1. 접근 방법

이번 문제는 Dijkstra 문제로, Dijkstra를 적용하면 쉽게 풀 수 있었다.

코드에다가 조금씩 설명을 적어놓을 것이다.

 

2. 코드

from typing import List
import heapq

INF = int(1e9)


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        def get_smallest_node():
            min_value = INF
            idx = 0
            for i in range(1, n + 1):
                if dist[i] < min_value and not visited[i]:
                    min_value = dist[i]
                    idx = i
            return idx

        graph = [[] for _ in range(n + 1)]

        for a, b, c in times:  # 노드 간선 정리, a: 출발 노드, b: 도착 노드, c: weight
            graph[a].append((b, c))

        visited = [False] * (n + 1)  # 방문 여부를 False로 표기
        dist = [INF] * (n + 1)  # distance에 대해서 infinte로 표기하여, 추후에 비교하여 더 작은 값을 넣을 수 있도록 함.

        visited[k] = True  # k를 출발로 삼음.
        dist[k] = 0

        for adj, d in graph[k]:  # 출발로 삼은 k에 대해서, 간선들을 정리해줌. 즉, k에서 출발하는 선들 넣어줌.
            dist[adj] = d

        for _ in range(n - 1):
            cur = get_smallest_node()  # weight가 가장 적은 값을 가지고 온다.
            visited[cur] = True  # 해당 노드 방문 처리

            for adj, d in graph[cur]:  # 새로 방문한 곳에서 cost 새로 renewal하고,
                cost = dist[cur] + d
                if cost < dist[adj]:  # 기존 보다 값이 작다면, 대치시켜 줌.
                    dist[adj] = cost

        max_dist = max(dist[1:])  # 맨 0 번째 노드는 INF로 저장되어 있으므로, (1부터 노드 이용)
        if max_dist == INF:  # INF 가 존재한다면, 모든 노드를 방문 못하는 것이기 때문에 -1 반환
            return -1
        return max_dist


solution = Solution()
print(solution.networkDelayTime(times=[[1, 2, 1]], n=2, k=2))