[LeetCode] 743. Network Delay Time

 

 

문제 파악

-주어진 k부터 n까지 최소 거리를 구하는 문제

-다익스트라 함수 구현하기

-가중치 = 시간

접근 방법

-Edge, Entry 클래스로 구조체형태 만들기

-우선순위 큐를 활용해 거리가 짧은 노드들부터 순회

-큐에 들어간 원소를 전부 비워낼 때까지 while문 돌며 distance가 최소거리인지 체크

-(+) 그와 연결 된 노드들과의 거리도 최소거리인지 체크

-절대적인 최솟값 거리를 저장하는 distances 배열 통째로 리턴

⇒ 왜? 특정 노드 n까지의 최소거리가 아니라, 모든 노드를 순회할 때의 최솟값이기 때문.

(순서가 있는 그래프가 아니므로 n까지 != 최댓값임)

-리턴받은 최솟값 모음 배열을 돌며 가장 그 중 가장 오래 걸린 시간을 찾는다.(max)

코드 구현

import java.util.*;
class Solution {
    static class Edge{
        int to;
        int distance;
        public Edge(int to,int distance){
            this.to = to;
            this.distance=distance;
        }
    }
    static class Entry implements Comparable<Entry>{
        int node;
        int 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 i=0;i<times.length;i++){
            graph.putIfAbsent(times[i][0],new ArrayList<>());
            graph.get(times[i][0]).add(new Edge(times[i][1],times[i][2]));
        }
        int[] d = dijkstra(graph, k, n);

        int maxTime = 0;
        
        for (int i = 1; i <= n; i++) {
            if (d[i] == Integer.MAX_VALUE) {
                return -1; // 도달할 수 없는 노드가 있으면 -1을 반환
            }
            maxTime = Math.max(maxTime, d[i]);//갱신
        }
        //각 노드까지 최단거리를 담은 배열 중, 가장 큰 값이 모든 노드를 순회하는 최소 시간이다.
        return maxTime;
    }

    public int[] dijkstra(Map<Integer,List<Edge>> graph,int k,int n){
        int MAX=Integer.MAX_VALUE;
        int[] distances = new int[n+1];
        Arrays.fill(distances,MAX);//최솟값 구하기 위한 최댓값 초기화 셋팅

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

        while(!pq.isEmpty()){
            Entry curr = pq.remove();
            if(distances[curr.node] < curr.distance) continue;//갱신할필요X

            if (!graph.containsKey(curr.node)) continue;//연결된애없으면 return
            for(Edge e:graph.get(curr.node)){
                int sumDistance = curr.distance + e.distance;
                
                if(sumDistance<distances[e.to]){
                    distances[e.to]=sumDistance;
                    pq.add(new Entry(e.to,sumDistance));
                }
            }
        }
        return distances;
    }
}

배우게 된 점

-최소시간을 구하는 다익스트라 함수에서 최소거리를 통째로 리턴하여 그 중 최대값을 찾아야, 모든 노드 순회의 최솟값이 된다는것.