[리트코드] 743. Network Delay Time

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

문제를 읽어보면 방향 그래프와 가중치가 주어진 것을 확인할 수 있다.

우선 가중치가 주어진 그래프를 보고 다익스트라 알고리즘으로 풀 수 있지 않을까? 라는 생각을 하고 문제를 더 읽어보자

 

문제를 더 읽어보니 시작 노드가 주어지고 시작 노드에서 모든 노드까지 시그널이 전파되는데 걸리는 최소 시간을 구하는 문제이다.

만약 모든 노드에 시그널이 전파되지 못한다면 -1을 리턴하라고 한다.

 

시작 노드로 부터 각각의 노드에 도착하는 최단 시간들을 모두 구하고 그 중 최대 시간을 구하면 되는 문제이다. 

각각의 노드에 도착하는 최단 시간은 다익스트라 알고리즘을 통해 구할 수 있다.

 

 

문제 풀이

1. edge 에 대한 정보가 times 배열로 들어온다. 이 배열을 내가 사용하기 편한 구조로 변경하자!

2. 다익스트라 알고리즘을 사용하여 시작 지점부터 모든 지점의 도달할 수 있는 최단 시간을 구하자

3. 구한 최단 시간 중 최대 시간을 리턴한다. 만약 구하지 못한 최단 시간이 있다면 -1을 리턴하자

 

 

코드

import java.util.*;

class Solution {
    static final int INF = Integer.MAX_VALUE;
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();

        for (int[] time : times) {
            graph.putIfAbsent(time[0], new ArrayList<>());
            graph.get(time[0]).add(new int[]{time[1], time[2]});

        }

        int[] distance = new int[n+1];
        Arrays.fill(distance, INF);

        Queue<int[]> pq = new PriorityQueue<>((e1, e2) -> e1[1] - e2[1]);
        pq.add(new int[]{k, 0});
        distance[k] = 0;

        while (!pq.isEmpty()) {
            int[] cur = pq.remove();

            if(distance[cur[0]] < cur[1]) continue;

            if(graph.containsKey(cur[0])){
                for(int[] next : graph.get(cur[0])){
                    int nextNode = next[0];
                    int nextDist = cur[1] + next[1];

                    if(nextDist < distance[nextNode]){
                        pq.add(new int[]{nextNode, nextDist});
                        distance[nextNode] = nextDist;
                    }
                }
            }
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            if(distance[i] == INF){
                return -1;
            }
            max = Math.max(max, distance[i]);
        }

        return max;
    
    }
}