[Leetcode 아주 상세한 문제풀이] 743. Network Delay Time - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 743번 문제 Network Delay Time 다.

우선 문제를 살펴보자.

 

리트코드 743번 문제 Network Delay Time 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

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

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

Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
 
Constraints:
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

 

 

문제 설명

문제를 간략히 살펴보자. Network를 표현하는 1부터 n까지 n개의 노드가 주어진다. 또한 노드 사이 이동 시간을 나타내는 배열도 주어진다. 이 배열은 3개의 element times[i] = (ui, vi, wi)로 주어지는데 ui는 시작점, vi는 도착점, 그리고 wi는 걸리는 시간을 의미한다.

이 문제에서는 특정 노드 k로 부터 시작하는 시그널을 모든 노드에 도착할 때 까지 걸리는 최소 시간을 구해야 한다. 만약 전체 노드에 도달할 수 없다면 -1을 리턴하면 된다. 만약 문제 예시 1번과 같이 4개의 노드가 주어지고 각 노드 간 이동 시간이 주어져 있다고 보자. 이때 시작 노드 (=k)가 2로 주어져 있다면 노드1까지는 1, 노드 3까지는 1, 그리고 노드 4까지는 2 (=1+1) 걸리므로 모든 노드에 시그널이 도착하는 최소 시간을 2라고 할 수 있다.

이제 문제를 한 번 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 해결하기 위해서는 Dijkstra's algorithm에 대해 이해해야 한다.

Dijkstra's algorithm은 그래프에서 여러 노드가 있을 때 가장 짧은 거리를 찾아내는 방법이다.

이 문제의 경우 먼저 주어진 노드들을 가지고 그래프를 만들어야 한다.

이때 각 노드들 사이에 이동 시간을 같이 부여한다.

그 후 Dijkstra's algorithm을 이용하여 시작점으로부터 모든 노드에 도착하기까지 최단 거리를 구한다.

이때 알고리즘은 다음 노드까지 최단 이동 시간을 찾기 위해 priority queue (min-heap)을 유지한다.

모든 노드 탐색 후 도달할 수 없는 노드가 있는지 확인한다.

만약 모든 노드를 탐색 가능하다면 어떤 노드든 '최대' 이동 시간을 구한다.

우리는 탐색 가능한 모든 노드를 탐색했으므로 이때 '최대' 이동 시간이 우리가 찾던 답이 된다.

Dijkstra's algorithm 이란

디익스트라 알고리즘(Dijkstra's algorithm)은 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 비비안 디익스트라(Edsger Wybe Dijkstra)가 1956년에 고안했다. 주로 가중치가 있는 그래프에서 사용되며, 각 간선의 가중치는 음이 아닌 값을 가져야 한다. 디익스트라 알고리즘의 기본 원리는 다음과 같다.

1) 초기화: 시작 노드를 제외한 모든 노드의 최단 거리 추정치를 무한대로 설정한다. 시작 노드의 최단 거리 추정치는 0으로 설정한다.

2) 노드 방문: 아직 방문하지 않은 노드 중에서 최단 거리 추정치가 가장 작은 노드를 선택한다. 이 노드를 현재 노드로 설정한다.

3) 경로 갱신: 현재 노드에 인접한 아직 방문하지 않은 노드들의 최단 거리 추정치를 갱신한다. 만약 현재 노드를 거쳐서 이웃 노드로 가는 거리가 기존에 알려진 최단 거리보다 작다면, 최단 거리 추정치를 갱신한다.

4) 반복: 모든 노드가 방문될 때까지 2번과 3번 과정을 반복한다.

5) 결과: 시작 노드로부터 다른 모든 노드까지의 최단 경로와 그 거리가 결정된다.

디익스트라 알고리즘은 우선순위 큐(최소 힙)를 사용하여 효율적으로 최단 거리가 가장 작은 노드를 찾을 수 있다. 이 알고리즘은 네트워크 라우팅, 지도에서의 경로 찾기 등 다양한 분야에서 활용된다.

 

 

문제 풀이

Heap을 사용하기 위하여 heapq module을 가져온다. (line 1)

솔루션을 찾기 위하여 인풋을 입력받기 위한 함수를 정의한다. (line 3)

먼저 인풋을 바탕으로 그래프를 만들어준다. (line 4)

이때 그래프는 시작노드와 도착노드 그리고 그 둘 사이 이동 시간으로 구성된다. (line 5)

그 후 Dijkstra's algorithm을 이용하여 최단 거리를 찾을 것이다.

우선 최소 시간은 무한대 (inf)로 초기화를 시켜준다. (line 10)

그리고 시작 노드의 최소 시간은 0으로 초기화를 시켜준다. (line 11)

또한 heap 역시 초기화를 시켜주는데 여기서 0을 k 노드로부터 이동 시이며 k노드가 시작점임을 의미한다. (line 12)

Heap이 존재하는한 탐색을 계속한다. (line 14)

이때 heap에 있는 현재 탐색 노드와 그때 이동 시간을 가져온다. (line 15)

그리고 현재 노드까지 이동 시간이 지금까지 탐색한 최소 이동시간과 비교한다.

만약 현재 노드까지 이동 시간이 지금까지 탐색한 최소 이동시간보다 더 크다면 탐색을 계속한다. (line 16)

그 후 그래프에서 해당 노드 k에서 갈 수 있는 노드와 그 이동 시간을 탐색한다. (line 18)

이때 새로운 이동 시간은 현재 탐색하고 있는 노드가지 이동시간에 새로운 노드까지 이동 시간을 합한 것이다. (line 19)

만약 그 새로운 이동 시간이 도착 가능한 노드까지 시간보다 작다면 최소 이동 시간을 업데이트 해준다. (line 20-21)

그리고 추후 검색을 위하여 새로운 시간과 노드를 heap에 추가해준다. (line 22)

모든 탐색을 마치고 나면 도착 가능한 노드들의 탐색을 마쳤다.

이때 최소 이동 시간 중 최대값을 찾아낸다. (line 25)

이것이 우리가 찾고자 하는 값이므로 이 값을 리턴한다. (line 26)

만약 max_time이 무한대로 남아있다면 도착 가능한 노드들이 없었다는 뜻이므로 -1을 리턴한다.

 

 

문제 풀이 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.longest = 0
 
        def dfs(node):
            if not node:
                return 0
 
            left_length = dfs(node.left)
            right_length = dfs(node.right)
 
            left_path = right_path = 0
 
            if node.left and node.left.val == node.val:
                left_path = left_length + 1
 
            if node.right and node.right.val == node.val:
                right_path = right_length + 1
 
            # Update the longest path found so far
            self.longest = max(self.longest, left_path + right_path)
 
            # Return the length of the longest path ending at this node
            return max(left_path, right_path)
 
        dfs(root)
        return self.longest
 
# Example usage
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(1)
root.right.right = TreeNode(5)
 
sol = Solution()
print(sol.longestUnivaluePath(root))  # Output: 2
 

 

 

743. Network Delay Time