[LeetCode] Network Delay Time - Java(자바)

문제

Network Delay Time(https://leetcode.com/problems/network-delay-time)

문제 설명

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = ($u_{i}$, $v_{i}$, $w_{i}$), where $u_{i}$ is the source node, $v_{i}$ is the target node, and $w_{i}$ is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

문제 해석

• 1~n개의 노드로 구성된 네트워크가 제공된다.
• [출발 노드 번호, 도착 노드 번호, 걸리는 시간]이 저장된 2차원 배열 times도 제공된다.
• 노드 k에서 신호를 보낼 때, 모든 노드에 신호가 도달하는 최소 시간을 반환하라. 만약 모든 노드에 신호가 도달하는 것이 불가능하면 -1을 반환하라.

제한사항

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

입출력 예

Example 1:

• Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
• Output: 2

Example 2:

• Input: times = [[1, 2, 1]], n = 2, k = 1
• Output: 1

Example 3:

• Input: times = [[1, 2, 1]], n = 2, k = 2
• Output: -1

풀이

문제 파악

• times 배열은 노드와 노드 간의 간선에 대한 이동시간을 담은 배열
  • 해당 배열을 인접 리스트로 변환해 노드 별 정보를 저장하도록 한다.
• 문제에서 요구하는 최소 시간은 다익스트라로 구한 노드 별로 도달하는 모든 시간 중 최대 시간과 같음
  • 다익스트라로 도출된 최대 시간이 모든 노드에 도달할 경우의 시간이 됨

접근 방법

1. 출발/도착 노드와 이동 시간에 대한 배열을 인접 리스트로 변환
2. 다익스트라 실행 시 먼저 각 노드에 도달할 때 걸리는 시간을 저장할 time 배열을 선언하고 모든 값을 Integer.MAX_VALUE로 초기화
3. 우선 순위 큐를 초기화하고 큐에 시작 노드와, 소요시간 0을 주고 다익스트라 로직 시작
   • dijkstra(): 현재 노드의 정보를 저장하고 현재 노드에서 접근할 수 있는 노드들에 대해 걸리는 시간이 기존에 저장한 시간보다 적게 걸릴 경우 distance 배열의 값을 갱신하고 큐에 해당 노드를 add
4. 다익스트라 실행 루프가 끝났을 경우 find 함수에 distance 배열과 노드의 수 n를 주고 실행
   • find(): 배열 내에 MAX_VALUE 값이 있다면 -1(도달하지 못한 노드가 존재한다는 의미), 없다면 maxTime을 배열 내 최대값으로 갱신하고(배열이 모든 노드에 도달할 때 최소 시간을 저장해둔 것이므로 이 중 최대값은 모든 노드에 도달할 때의 시간을 의미) maxTime 반환

코드 구현

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for(int[] time : times) {
            // u -> v 로 가는 경로와 가중치 w를 그래프에 추가
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        return dijkstra(graph, k, n);
    }

    private int dijkstra(Map<Integer, List<int[]>> graph, int start, int n) {
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
        pq.add(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int node = cur[0];
            int time = cur[1];

            if (time > distance[node]) continue;

            // 인접 노드 확인
            for (int[] edge : graph.get(node)) {
                int nextNode = edge[0];
                int nextTime = time + edge[1];

                if (nextTime < distance[nextNode]) {
                    distance[nextNode] = nextTime;
                    pq.add(new int[]{nextNode, nextTime});
                }
            }
        }
        return find(distance, n);
    }
    
    private int find(int[] distance, int n) {
        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            maxTime = Math.max(maxTime, distance[i]);
        }

        return maxTime;
    }
}