Today's Challenge

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

Network Delay Time - LeetCode

DFS/BFS/다익스트라 중에 하나 취사선택해서 풀면 되는 문제.
다른 건 모르겠고, defaultdic로 adjacent array를 쉽게 만들 수 있다는 걸 배움.

# BFS
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))
            
        max_delay = 0
        edges, visited = [], [k]
        curr_node, curr_delay = k, 0
        
        while len(visited) < n:
            for v, w in adj[curr_node]:
                edges.append((v, w + curr_delay))
            edges.sort(key=lambda pair: pair[-1], reverse=True)
            
            i = len(edges) - 1
            while i >=0 and edges[i][0] in visited:
                edges.pop(i)
                i -= 1
            if i == -1:
                break
            
            curr_node, curr_delay = edges.pop(i)
            visited.append(curr_node)
            max_delay = max_delay if max_delay > curr_delay else curr_delay
            
        if len(visited) < n:
            return -1
        
        return max_delays

# Dijkstra
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((w, v))
            
        visited = set()
        heap = [(0, k)]
        
        while heap:
            travel_time, node = heapq.heappop(heap)
            visited.add(node)
            
            if len(visited) == n:
                return travel_time
            
            for time, adj_node in adj[node]:
                if adj_node not in visited:
                    heapq.heappush(heap, (travel_time+time, adj_node))
                
        return -1