[LeetCode] 743. Network Delay Time (swift, python)

Network Delay Time - LeetCode

 

풀이

 다익스트라 알고리즘을 활용해서 풀 수 있는 문제. 시작점 k에서 모든 노드까지의 최단거리를 구해준다. distance 배열에 k에서 각 노드 까지의 최단거리가 구해진다.

 문제에서 모든 노드에 신호를 보내기까지 걸리는 시간을 구하라 했으므로 distance 배열에서 가장 큰 값(걸리는 시간이 가장 큰 경우)이 문제의 답이 된다. 만약 k에서 시작해서 도달할 수 없는 노드가 있을 경우에는 모든 노드에 신호를 보낼 수 없는 경우(impossible)이므로 -1을 리턴해주면 된다.

 

코드

[swift]

typealias nodeTuple = (Int, Int)
 
class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        var graph = Array(repeating: [nodeTuple](), count: n+1)
        var distance: [Int] = Array(repeating: Int(1e9), count: n+1)
        
        for time in times {
            graph[time[0]].append((time[1], time[2]))
        }
        
        var queue: [nodeTuple] = []
        queue.append((0, k))
        distance[k] = 0
        
        while !queue.isEmpty {
            queue.sort(by: { $0.0 > $1.0 })
            let tuple: nodeTuple = queue.removeFirst()
            let dist: Int = tuple.0
            let now: Int = tuple.1
            
            if distance[now] < dist {
                continue
            }
            
            for g in graph[now] {
                let cost: Int = dist + g.1
                
                if cost < distance[g.0] {
                    distance[g.0] = cost
                    queue.append((cost, g.0))
                }
            }
        }
        
        var answer: Int = 0
        
        for i in 1...n {
            answer = max(answer, distance[i])
        }
        
        // 최단거리를 담는 배열에 INF와 같은 값이 있다면 k에서 모든 노드를 방문할 수 없다는 뜻이므로
        // -1을 리턴
        if answer == Int(1e9) {
            return -1
        }
        
        return answer
    }
}
 
 
let sol = Solution()
print(sol.networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))
 

 

[python] 

pyimport heapq
INF = int(1e9)
 
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n+1)]
        distance = [INF] * (n+1)
 
        for (a, b, c) in times:
            graph[a].append((b, c))
        
        q = []
        heapq.heappush(q, (0, k))
        distance[k] = 0
 
        while q:
            dist, now = heapq.heappop(q)
            
            if distance[now] < dist:
                continue
 
            for (node, nodeDist) in graph[now]:
                cost = dist + nodeDist
 
                if cost < distance[node]:
                    distance[node] = cost
                    heapq.heappush(q, (cost, node))
        
        answer = 0
 
        for i in range(1, n+1):
            answer = max(answer, distance[i])
        
        # 최단거리를 담는 배열에 INF와 같은 값이 있다면 k에서 모든 노드를 방문할 수 없다는 뜻이므로
        # -1을 리턴
        if answer == INF:
            return -1
        return answer