[LeetCode] 743. Network Delay Time (java)

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

 

 

문제 파악

• 주어진 정보
  
  • 1부터 n까지 라벨링 된 n개의 노드가 있는 네트워크 times
  • tims[i] = (ui, vi, wi) → ui에서 vi 노드까지 신호를 보내는데 wi 시간이 걸린다.
• 목표
  • k노드로부터 n개의 모든 노드가 신호를 받는데 걸리는 최소 시간
  • 단, n개의 모든 노드가 신호를 받는 것이 불가능하다면 -1을 반환

 

문제 풀이

Dijkstra (다익스트라)

package main.java.LeetCode;

import java.util.*;

class NetworkDelayTime {
    public int networkDelayTime(int[][] times, int n, int k) {
        // times -> 그래프 변환
        Map<Integer, List<Edge>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] time : times) {
            graph.get(time[0]).add(new Edge(time[1], time[2]));
        }

        int[] timeSum = new int[n + 1];
        Arrays.fill(timeSum, Integer.MAX_VALUE);

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

        while (!pq.isEmpty()) {
            Entry curr = pq.remove();
            if (curr.timeSum > timeSum[curr.node]) continue;

            for (Edge edge : graph.get(curr.node)) {
                int newTimeSum = curr.timeSum + edge.time;
                if (newTimeSum < timeSum[edge.to]) {
                    pq.add(new Entry(edge.to, newTimeSum));
                    timeSum[edge.to] = newTimeSum;
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (timeSum[i] == Integer.MAX_VALUE) return -1;

            answer = Math.max(timeSum[i], answer);
        }

        return answer;
    }

    class Edge {
        int to;
        int time;

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

    class Entry implements Comparable<Entry> {
        int node;
        int timeSum;

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

        @Override
        public int compareTo(Entry e) {
            return this.timeSum - e.timeSum;
        }
    }
}

 

📊 실행 결과

 

 

NOTE

• 리스트는 add, 맵은 put 메서드로 저장
• Arrays.fill( , );
• 오버라이딩 메서드 compareTo()에 @Override, public 붙여주기