leetcode 릿코드 743: network delay time / 다익스트라 풀이

문제: 릿코드 743 네트워크 딜레이 타임

1-n 까지의 노드와 함께 times 배열이 주어집니다. 

times[i] = (ui, vi, wi) 이런 형식으로 주어지며,

ui 는 시작노드, vi 는 타겟노드, wi는 거리입니다.

시그널을 k번째 노드에서부터 보내기 시작했을때

모든 노드에 시그널이 도달하는데 걸리는 최소시간을 찾는 문제입니다.

모든 노드에 도달 할 수 없는 경우엔 -1 을 리턴합니다

 

 

 

 

 

 

 

 

 

 

 

 

풀이: 

제한사항을 보면 단방향 엣지가 항상 양수이기 때문에

다익스트라 알고리즘을 통해 문제풀이가 가능합니다.

 

 

 

 

 

 

 

 

모든 노드에 시그널이 도달하는 시간 = 출발노드에서 가장 멀리 떨어져 있는 노드 사이의 거리를 리턴하면 됩니다.

 

자바 코드:

2차원 배열리스트를 이용해 그래프를 작성했으며

우선순위 큐를 이용해 아직 방문하지 않은 노드중 가장 값이 작은 노드를 선택합니다.

dist 배열에 노드간의 거리정보를 담은 후 마지막 for룹에서 가장 큰 max 값을 찾아냈습니다.

max 값을 찾는 도중 초기화 값이 그대로 담긴 노드가 있다면 방문이 불가능한 노드가 있다는 뜻이기 때문에 -1을 리턴합니다.

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
        for(int i = 0; i < n+1; i++){
            graph.add(new ArrayList<>());
        }
        for(int i = 0; i < times.length; i++){
            graph.get(times[i][0]).add(new int[]{times[i][1], times[i][2]});
        }
        int[] dist = new int[n+1];
        for(int i = 1; i < n+1; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[k] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
        pq.offer(new int[]{k, 0});
        while (!pq.isEmpty()){
            int[] cur = pq.poll();
            if(dist[cur[0]] < cur[1]){
                continue;
            }
            for(int i = 0; i < graph.get(cur[0]).size(); i++){
                int[] adj = graph.get(cur[0]).get(i);
                if(dist[adj[0]] > cur[1] + adj[1]){
                    dist[adj[0]] = cur[1] + adj[1];
                    pq.offer(new int[]{adj[0], dist[adj[0]]});
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < n+1; i++){
            if (dist[i] == Integer.MAX_VALUE){
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }
        
        return ans;
    }
}

결과:

시간과 메모리 제한 모두 안정적으로 통과합니다.