[LeetCode#743] Network Delay Time

 

❒ Description

---

제목	Network Delay Time
링크	https://leetcode.com/problems/network-delay-time/description/
자료구조/알고리즘	그래프 / 다익스트라 알고리즘
시간 복잡도	O(ElogV)

 

다익스트라 알고리즘을 사용해서 해결할 수 있는 문제이다.

이번 문제는 중복을 허용하지 않기 위해서 visited boolean 배열을 사용하였다.

 

 

문제 해결 순서

1. 주어진 input, times를 배열을 사용해서 표현해준다.
   • List<List<int[]>> : index는 source를 표현한다.
2. 각 노드까지 걸리는 소요시간을 나타내는 배열을 생성한다.
   • 배열 생성 후 최초에는 무한대 값을 의미하는 1e9로 초기화 한다.
3. 방문 여부를 확인할 배열을 생성한다.
4. 소요 시간이 짧은 순서가 우선이 되는 Priority Queue를 생성한다.
   • 최초 진입 점은 input으로 주어진 k이며, 소요 시간은 0으로 생각해야 한다.
5. Priority Queue가 빌 때 까지 반복한다.
   • PQ의 가장 앞 요소를 remove 한다.
   • 방문 여부를 확인한다. (재 방문한 노드라면 skip)
   • 방문한 곳에서 갈 수 있는 모든 노드를 탐색한다.
     • 더 짧은 경로로 노드를 방문했다면 2번에서 생성한 배열의 요소를 update
6. 결과 출력
   • 모든 노드가 신호를 수신하는데 걸리는 최소 시간을 계산해야 한다.
   • 즉, 모든 노드 중에서 가장 신호를 늦게 받는 노드의 시간이 정답이 된다.
   • 만약 방문하지 못한 노드가 있을 경우 -1을 반환한다.

 

 

 

 

 

❒ Solution

---

public int networkDelayTime(int[][] times, int n, int k) {
    // #1
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i <= n i++) graph.add(new ArrayList<>());
    for (int[] time : times) {
    	int source = time[0], target = time[1], time = time[2];
        graph.get(source).add(new in[]{target, time});
    }
    
    // #2
    int[] distance = new int[n+1];
    Arrays.fill(distance, 1e9);
    result[k] = 0;

    // #3
    boolean[] visited = new boolean[n+1];
    
    // #4
    Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t[1]));
    pq.offer(new int[]{k,0});
    
    // #5
    while (!pq.isEmpty()) {
        int[] node = pq.remove();
        int target = node[0], time = node[1];
        
        if (visited[target]) continue;
        visited[target] = true;
        
        for (int[] node : graph.get(target)) {
            int nextTarget = node[0];
            int nextTime = node[1];
            int totalTime = time + nextTime;
            if (totalTime < distance[nextTarget]) {
            	distance[target] = totalTime;
                pq.offer(target, distance[target]);
            }
        }
    }
    
    // #6
    int answer = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
    	if (distance[i] == Integer.MIN_VALUE) return -1;
        answer = Math.min(answer, result[i]);
    }
    return answer;
}

 

 

 

 

 

---