[TIL_Carrotww] 100 - 23/02/13

📝Carrotww의 코딩 기록장

🧲 python algorithm interview

🔍 Leetcode 743 Network Delay Time - Medium

예전에 풀었던 문제이다.
bfs와 heapq를 사용하여 풀 수 있는 문제이다.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        from collections import defaultdict
        import heapq

        path = defaultdict(list)
        dist = defaultdict(list)

        for start, end, time in times:
            path[start].append([end, time])

        queue = [[0, k]]

        while queue:
            time, node = heapq.heappop(queue)
            if node not in dist:
                dist[node] = time
                for n_node, n_time in path[node]:
                    heapq.heappush(queue, [time + n_time, n_node])

        if len(dist) == n:
            return max(dist.values())

        return -1

path에 갈 수 있는 node와 걸리는 시간 time을 넣어준다.
while문을 돌리며 dist 에 존재하지 않으면 dist에 추가를 해준다.
존재하지 않을때 추가해 주는 이유는 이미 값이 있다면 그건 이미 최소 도착이 아니기 때문이므로 값이 없을때 dist에 해당 node까지 걸리는 time을 넣어준다.

알다싶이 heappop을 하여 time 기준으로 최소 시간을 뽑아준다.

🧲 잡담

🔍 면접 준비를 하고있어 많은 문제를 풀지는 못한다 ㅠ
면접 잘 보고 다시 알고리즘 달려야지...