LeetCode 743. Network Delay Time

파이썬 알고리즘 인터뷰 문제 40번(리트코드 743번) Network Delay Time
https://leetcode.com/problems/network-delay-time/

나의 풀이

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        result = [float("inf")] * n
        result[k - 1] = 0
        
        for a, b, c in times:
            graph[a].append((b, c))
        
        left = set(graph)
        search = k
        
        if k not in left:
            return -1
        
        while left:
            for neighbor in graph[search]:
                result[neighbor[0] - 1] = min(result[neighbor[0] - 1], result[search - 1] + neighbor[1])
            left.remove(search)
            if left:
                search = min(left, key = lambda x: result[x - 1])
            
        result = max(result)
        if result == float("inf"):
            return -1
        else:
            return result

다른 풀이1

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        
        for vertex, neighbor, time in times:
            graph[vertex].append((neighbor, time))
        
        Q = [(0, k)]
        dist = collections.defaultdict(int)
        
        while Q:
            time, vertex = heapq.heappop(Q)
            if vertex not in dist:
                dist[vertex] = time
                for neighbor, delta in graph[vertex]:
                    heapq.heappush(Q, (time + delta, neighbor))

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

다른 풀이2

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        
        for vertex, neighbor, time in times:
            graph[vertex].append((neighbor, time))
        
        Q = [(0, k)]
        dist = collections.defaultdict(int)
        
        while Q:
            time, vertex = heapq.heappop(Q)
            if vertex not in dist:
                dist[vertex] = time
                if len(dist) == n: # 여기로 옮기면 더 빨라진다.
                    return max(dist.values())
                for neighbor, delta in graph[vertex]:
                    heapq.heappush(Q, (time + delta, neighbor))

        return -1

배운 점

• 아래는 최단 거리를 구하는 방법으로 대표적인 알고리즘이다.
• 다익스트라 알고리즘(Dijkstra Algorithm),
  벨만-포드 알고리즘(Bellman-Ford Algorithm),
  플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)
• 그 특징을 간단히 정리하면.

알고리즘	시간 복잡도	방식	특징 및 장점	단점 및 비효율성
다익스트라 (우선순위 큐)	(O((E + V) log V))	우선순위 큐(힙) 활용	- 한 출발점에서 모든 노드까지 최단 경로 - 효율적인 성능	- 음수 가중치 불가능
벨만-포드	(O(VE))	반복적인 간선 갱신	- 음수 가중치 가능 - 구현이 다익스트라보다 간단	- 성능이 다익스트라보다 떨어짐
플로이드-워셜	(O(V^3))	동적 계획법	- 모든 노드 간 최단 거리 계산 가능 - 그래프가 작은 경우 유용	- 시간 복잡도가 너무 높음