[Java] 네비게이션 테스트 - 최단 거리

1. 문제

네이게이션 시스템을 개발하기 위해 최단 거리를 계산하는 프로그램을 만들고 테스트하려 한다.

최단 거리를 계산하고자 하는 공간에는 총 N 개의 장소가 존재한다.

a 번째 장소에서 b 번째 장소로 이동하는 데에 걸리는 시간 time 이 edge[i] = {a, b, time} 로 주어진다고 하자.

 

당신은 0 번째 장소에 있다고 할 때, 최단 거리로 도달하는 데에 가장 오래 걸리는 장소의 인덱스를 출력하시오.

 

단, 정답이 여럿일 경우 더 작은 인덱스를 반환하시오.

 

 

 

2. 입력설명

• 0 < N <= 1000
• 0 < edge.length <= 10000

 

 

3. 출력 설명

도달하는데에 가장 오래 걸리는 장소의 인덱스를 출력

 

 

 

4. 매개변수 형식

N = 5

edge = {{0, 1, 5} , {0, 2, 7}, {1, 3, 10}, {3, 4, 8}, {2, 4, 9}, {4, 2, 1}}

 

 

5. 반환값 형식

4

 

 

6. 입출력 예시 설명

 

각 장소는 아래와 같이 구성되며, 최단 거리가 가장 먼 장소는 4 임을 알 수 있다.

 

 

 

 

7. 코드 구현

import java.util.*;

class Solution {
    List<List<int[]>> adjList;
    int N;

    public int solution(int N, int[][] edge) {
        // 다익스트라 문제
        this.N = N;
        adjList = new ArrayList<>(N);

        for (int i = 0; i < N; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] inits : edge) {
            int start = inits[0];
            int end = inits[1];
            int distance = inits[2];

            adjList.get(start).add(new int[]{end, distance});
        }

        int[] dists = dijkstra(0);

        int maxIndex = -1;
        int maxVal = -1;

        for (int i = 0; i < N; i++) {
            if (dists[i] > maxVal) {
                maxVal = dists[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    int[] dijkstra(int node) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(
                Comparator.comparingInt(a -> a[0])
        );

        int[] distances = new int[N];
        Arrays.fill(distances, Integer.MAX_VALUE);

        pq.offer(new int[]{0, node});
        distances[node] = 0;

        while (!pq.isEmpty()) {
            int[] ints = pq.poll();
            int dist = ints[0];
            int i = ints[1];

            if (distances[i] < dist) {
                continue;
            }

            for (int[] ints1 : adjList.get(i)) {
                int currentNode = ints1[0];
                int currentDist = ints[1];
                int newDist = dist + currentDist;
                if(distances[currentNode] > newDist) {
                    distances[currentNode] = newDist;
                    pq.offer(new int[]{newDist, currentNode});
                }
            }
        }
        return distances;
    }
}