743 - Network Delay Time

info

• 문제 보기: 743 - Network Delay Time
• 소요 시간: 23분 39초
• 풀이 언어: java
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

다익스트라

풀이 코드

info

• 메모리: 48900 KB
• 시간: 10 ms

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] adj = new ArrayList[n+1]; // 1 ~ n
        for (int i = 1; i < n+1; ++i) adj[i] = new ArrayList<>();
        for (int[] data : times) adj[data[0]].add(new int[]{data[1], data[2]});

        int[] minTime = new int[n+1];
        Arrays.fill(minTime, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));
        minTime[0] = minTime[k] = 0;
        pq.add(new int[]{k, 0}); // node, time

        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            int cur = e[0];
            int time = e[1];
            for (int[] data : adj[cur]) {
                int nxt = data[0];
                int w = data[1];
                if (minTime[nxt] <= time + w) continue;
                minTime[nxt] = time + w;
                pq.add(new int[]{nxt, time+w});
            }
        }

        int ans = 0;
        for (int v : minTime) {
            if (v == Integer.MAX_VALUE) return -1; // not reachable
            ans = ans < v ? v : ans;
        }

        return ans;
    }
}

풀이 해설

주어진 특정 노드 k로부터 전체 노드에 도달하기까지 최소 시간을 구하는 문제이다.

음수가 없는 가중치 그래프이므로 다익스트라를 적용할 수 있다.

$\text{minTime[i]} = \text{local minimum time from } k \text{ to } i$ 이라고 정의하고,

다익스트라 실행 후 minTime 배열의 최대값을 리턴하면 된다. (전부 도달 못하는 경우는 -1 처리)

메모

• 대회 연습 목적이라면 PriorityQueue를 안 쓰는게 좋고, 코테 연습 목적이라면 쓰는게 좋다.