[백준/JAVA] BOJ 22865 - 가장 먼 곳

내가 좋아하는 다익스트라 ^3^ 문제 편식 그만해야 하는데...

👀 문제

22865번: 가장 먼 곳 ✨ 골드 4

$N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다.

이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다.

예를 들어, $X$ 위치에 있는 집에서 친구 $A$, $B$, $C$의 집까지의 거리가 각각 3, 5, 4이라 가정하고 $Y$ 위치에 있는 집에서 친구 $A$, $B$, $C$의 집까지의 거리가 각각 5, 7, 2라고 하자.

이때, 친구들의 집으로부터 땅 $X$와 땅 $Y$ 중 더 먼 곳은 땅 $X$이다. 왜냐하면 $X$에서 가장 가까운 친구의 집까지의 거리는 3이고, $Y$에서는 $2$이기 때문이다.

친구들이 살고 있는 집으로부터 가장 먼 곳을 구해보자.

예제 입력

6
1 2 5
8
1 2 1
2 3 4
1 4 2
2 5 3
1 6 5
5 6 2
3 4 2
4 5 6

예제 출력

3

🔑 키포인트

다익스트라 최단 경로

✍️ 코드

📍 처음에 문제 이해를 잘못해서 틀린...

🤔 각 친구 a, b, c에서 각 집의 거리를 dist[3][n+1] 배열에 저장하고, 반복문 돌려서 비교해 줬어요

💡 dist를 2차원 배열로 만들었던 것 빼고는 일반적인 다익스트라 문제와 같음

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

public class BOJ22865_가장먼곳 {
    static class Node implements Comparable<Node> {
        int x, dist;

        Node(int x, int dist) {
            this.x = x;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

    static int n, cnt;
    static ArrayList<ArrayList<Node>> graph;
    static PriorityQueue<Node> pq;
    static int[][] dist;
    static int[] friends;
    static int maxDist, answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        friends = new int[3];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 3; i++) {
            friends[i] = Integer.parseInt(st.nextToken());
        }

        graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            graph.get(a).add(new Node(b, d));
            graph.get(b).add(new Node(a, d));
        }

        // 각 친구 집별로의 거리 저장하기
        dist = new int[3][n + 1];
        for (int[] d : dist) {
            Arrays.fill(d, Integer.MAX_VALUE);
        }

        // 각 친구의 집에서 다른 집까지의 거리 구하기
        for (int friend : friends) {
            pq = new PriorityQueue<>();
            pq.offer(new Node(friend, 0));
            dist[cnt][friend] = 0;
            cal();
            cnt++;
        }

        // 1 ~ n 집 중에 친구들과의 최소 거리가 가장 큰 집 찾기
        for (int i = 1; i < n + 1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < 3; j++) {
                min = Math.min(min, dist[j][i]);
            }
            if (min > maxDist) {
                maxDist = min;
                answer = i;
            }
        }
        System.out.println(answer);
    }

    // 다익스트리
    static void cal() {
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            for (Node next : graph.get(now.x)) {
                if (dist[cnt][next.x] > dist[cnt][now.x] + next.dist) {
                    dist[cnt][next.x] = dist[cnt][now.x] + next.dist;
                    pq.offer(new Node(next.x, dist[cnt][next.x]));
                }
            }
        }
    }
}