[LeetCode/Java] Network Delay Time

문제

https://leetcode.com/problems/network-delay-time/description/

---

문제 파악

• n개의 노드, 출발노드 k, 각 노드의 연결 관계와 이동 시간이 주어진다.
• 출발노드로 부터 모든 노드에 네트워크 신호를 전달하기까지 걸리는 최소 시간을 구하는 문제
• 네트워크 신호는 연결된 노드로 동시에 퍼져나간다

---

접근 방법

• 출발 노드와 가장 멀리 떨어진 노드에 신호가 도착 ! → 모든 노드들에 신호 도착 의미
• 시작노드 k 에서부터 가장 멀리 있는 노드간의 거리만 확인하면 모든 노드에 신호가 전달되는데 걸리는 최소시간을 구할 수 있음

---

코드 구현

import java.util.*;

class Solution {
    static class Edge {
        private int to, distance;

        public Edge(int to, int distance) {
            this.to = to;
            this.distance = distance;
        }
    }

    static class Entry implements Comparable<Entry> {
        private int node, distance;

        public Entry(int node, int distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(Entry o) {
            return this.distance - o.distance;
        }
    }

    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int[] time : times) {
            // 출발 노드가 그래프에 없으면 빈 ArrayList를 추가
            graph.putIfAbsent(time[0], new ArrayList<>());
            // 출발 노드의 간선 리스트에 새로운 Edge를 추가
            graph.get(time[0]).add(new Edge(time[1], time[2]));
        }
        
        final int INF = Integer.MAX_VALUE;
        int[] distance = new int[n + 1];
        Arrays.fill(distance, INF);

        Queue<Entry> pq = new PriorityQueue<>();
        pq.add(new Entry(k, 0));
        distance[k] = 0;

        while (!pq.isEmpty()) {
            Entry current = pq.remove();
            if (distance[current.node] < current.distance)
                continue;
            // graph.containsKey : 특정 키가 맵에 존재하는지 확인
            if (graph.containsKey(current.node)) {
                for (Edge edge : graph.get(current.node)) {
                    int newDist = current.distance + edge.distance;
                    if (newDist < distance[edge.to]) {
                        distance[edge.to] = newDist;
                        pq.add(new Entry(edge.to, newDist));
                    }
                }
            }
        }
        int maxTime = 0;
        for(int i = 1; i <= n; i++){
            if(distance[i] == INF) return -1; // 도달할 수 없는 노드가 있는 경우
            maxTime = Math.max(maxTime, distance[i]); // 최대 시간 : 가장 먼 노드까지 걸린 시간 = 모든 네트워크에 신호 전달
        }
        return maxTime;
    }
}

---

배우게 된 점

for (int i = 0; i < times.length; i++) {
     graph.put(times[i][0], List.of(new Edge(times[i][1], times[i][2])));
}

<처음 그래프 초기화시 위의 코드가 되지 않는 이유>

• List.of(new Edge(times[i][1], times[i][2]))를 사용하여 불변(immutable) 리스트를 생성
• 만약 동일한 출발 노드에 여러 간선이 존재하는 경우, 이전에 추가된 간선이 덮어쓰여지기 때문에 모든 간선 정보를 유지할 수 없음

예를 들어

• 만약 times 배열이 [[1, 2, 4], [1, 3, 2], [2, 3, 5]]인 경우, 그래프의 초기화 과정에서 graph.put(1, List.of(new Edge(2, 4)))로 인해 출발 노드 1의 간선 리스트는 [Edge(2, 4)]로 초기화
• 이후 graph.put(1, List.of(new Edge(3, 2)))로 인해, 출발 노드 1의 간선 리스트는 [Edge(3, 2)]로 덮어쓰여지게 됨
• 결과적으로, 출발 노드 1의 간선 정보는 Edge(2, 4)와 Edge(3, 2)가 아닌 Edge(3, 2)만 남게 됨