ch13-1(leetcode 743). 네트워크 딜레이 타임

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 743번 ( https://leetcode.com/problems/network-delay-time/ )

 

시도

class Solution(object):

    def networkDelayTime(self, times, n, k):
        if n == 1:
            return 0

        queue = collections.deque()
        visited = set()
        graph = collections.defaultdict(list)
        for a, b, c in times:
            graph[a].append([b, c])

        dist = collections.defaultdict(lambda:float('inf'))
        dist[k] = 0
        count = 0
        queue.append(k)

        while queue:
            node = queue.popleft()
            for k, v in graph[node]:
                if k not in visited:
                    dist[k] = min(dist[k], dist[node]+v)
                    queue.append(k)
            visited.add(node)
        
        result = max(dist, key=lambda x:dist[x])
        return dist[result] if len(dist) == n  else -1

 

풀이. (교재 참고)

다익스트라(Dijkstra) 알고리즘을 구현하는 문제이다. 

다익스트라 알고리즘은 BFS 탐색으로 구현되며, DFS와 달리 재귀함수로 처리할 수 없다. BFS 탐색을 할 때에는 큐를 사용한다. 

 

노드 A에 대해서 BFS를 실행하는 경우, A의 주변 노드의 값을 모두 업데이트하고 그 주변 노드들을 큐에 추가한다.

이후 A를 큐에서 제거하는 방식으로 구현한다. 

 

다만 A를 제거하고 큐에서 다음 값을 불러올 때는 값이 가장 작은 노드 순서대로 불러와야 한다. 

이런 정렬을 매번 따로 할 수도 있겠으나 교재에서는 힙(heap)과 heappush(), heappop()을 사용해서 힙 내부에서 자동으로 정렬이 되도록 구현하였다. 

 

우선, 힙을 사용하기 전에 노드 A와 A에서 신호를 보낼 수 있는 노드, 신호를 보내는 데 걸리는 시간 정보를 더 효율적인 자료구조에 넣을 필요가 있다. 

딕셔너리를 사용해서 노드 A를 key값으로, 뒤의 두 값을 하나의 튜플로 묶어서 A를 key값으로 하는 리스트의 원소로 추가하자. 

graph = collections.defaultdict(list)

for u, v, w in times:
    graph[u].append((v, w))

 

출발 노드 k로부터 노드 A까지 신호가 도달하는 시간을 저장하는 변수도 필요하다. O(1) 만에 조회할 수 있는 딕셔너리 형식으로 선언한다. 

값을 변경할 때는 기존의 값과, 주변 노드의 시간을 참고해서 새로 계산된 값 중에서 더 작은 값으로만 변경될 수 있도록 해야 한다. 

여기서는 힙을 사용하기 때문에 힙 내부에서 이미 정렬이 되고, 시간이 오래 걸리는 경우 힙의 뒤 순서에 위치하게 된다. 또한 이미 탐색한 노드는 탐색하지 않는 방법으로 이런 오류가 발생할 가능성을 없앴다. 

 

또한 모든 노드를 탐색할 수 있는 경로가 없다면 -1을 리턴해야 한다. 모든 노드가 탐색되지 않은 경우 dist 딕셔너리의 길이가 n개 미만일 것이므로, dist 길이를 확인해서 -1을 리턴할지, 최댓값을 리턴할지를 판단하자. 

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