[JAVA] 백준 22865 - 가장 먼 곳

https://www.acmicpc.net/problem/22865

N개의 도시 중 3개의 정점에서 가장 먼 곳을 찾는데, 가장 먼 곳 = 3개의 정점에서 가장 가까운 곳의 최댓값이다.

 

3개의 정점 정보를 입력받는데, 중복이 될 수 있으므로 distinct해서 관리하고,

distinct한 개수만큼 다익스트라를 돌린 뒤 각 정점간의 거리의 최솟값의 최댓값을 가진 정점의 index를 반환했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCount = par(br.readLine());
        int[] friendList = Arrays.stream(getArray(br.readLine())).distinct().toArray();
        int[][] dist = new int[friendList.length][nodeCount+1];
        int roadCount = par(br.readLine());
        List<List<P22865>> list = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < roadCount; i++) {
            int[] r = getArray(br.readLine());
            list.get(r[0]).add(new P22865(r[1],r[2]));
            list.get(r[1]).add(new P22865(r[0],r[2]));
        }
        for (int i = 0; i < friendList.length; i++) {
            Arrays.fill(dist[i],Integer.MAX_VALUE);
            int start = friendList[i];
            dist[i][start] = 0;
            dijkstra(dist[i],start,list);
        }
        int max = Integer.MIN_VALUE;
        int midx = -1;
        for (int i = 1; i <= nodeCount; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < friendList.length; j++) {
                min = Math.min(dist[j][i],min);
            }
            if(min>max){
                max = min;
                midx = i;
            }
        }
        System.out.println(midx);
    }

    static void dijkstra(int[] dist, int startNode, List<List<P22865>> list){
        PriorityQueue<P22865> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        pq.offer(new P22865(startNode));
        while(!pq.isEmpty()){
            P22865 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if(dist[value]<weight) continue;
            List<P22865> vList = list.get(value);
            for (int i = 0; i < vList.size(); i++) {
                P22865 road = vList.get(i);
                int to = road.to;
                int cost = road.weight;
                if(dist[to]>weight+cost){
                    P22865 offer = new P22865(to);
                    offer.weight = weight+cost;
                    dist[to] = weight+cost;
                    pq.offer(offer);
                }
            }
        }
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}
class P22865 implements Comparable<P22865> {
    int to;
    int weight = 0;

    P22865(int t){
        this.to = t;
    }
    P22865(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P22865 o) {
        return this.weight - o.weight;
    }
}