[백준] 1774번 - 우주신과의 교감 (Gold 3)

문제 링크

백준 1774번 - 우주신과의 교감 (Gold 3)

문제 설명

3차원 좌표 상의 N($\leq$ 1,000)개의 점이 주어져 있다.
이들 중 일부는 이미 연결된 상태이다. 이미 연결된 점들의 쌍은 M($\leq$ 1,000)개가 주어져 있다.
이 때, 모든 점들을 연결하기 위해 추가로 그려야하는 선분의 길이의 합의 최솟값을 구하시오.

정답 코드 및 설명

각 점을 하나의 노드로 보고, 이미 연결된 노드들을 잇는 간선의 가중치는 0, 이어져 있지 않은 노드들을 잇는 간선의 가중치는 두 점 사이의 거리인 그래프를 생각하자.
이 그래프의 최소 신장 트리를 구하고 총 비용을 구하면 답이 된다.

모든 노드가 이어진 완전그래프이므로 프림 알고리즘을 사용하였다.

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

public class BOJ1774 {
    final double INF = 2_000_000_000;
    int n;
    long[][] points;
    double[][] dist;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        points = new long[n][2];
        dist = new double[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            points[i][0] = Long.parseLong(st.nextToken());
            points[i][1] = Long.parseLong(st.nextToken());
            for (int j = 0; j < i; j++) {
                dist[i][j] = dist[j][i] = dist(points[i], points[j]);
            }
        }
        int cnt1, cnt2;
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            cnt1 = Integer.parseInt(st.nextToken()) - 1;
            cnt2 = Integer.parseInt(st.nextToken()) - 1;
            dist[cnt1][cnt2] = dist[cnt2][cnt1] = 0;
        }
    }

    double dist(long[] point1, long[] point2) {
        return Math.sqrt((point1[0] - point2[0]) * (point1[0] - point2[0]) +
                (point1[1] - point2[1]) * (point1[1] - point2[1]));
    }

    double Prim() {
        class God {
            final int godNo;
            final double minDist;

            public God(int godNo, double minDist) {
                this.godNo = godNo;
                this.minDist = minDist;
            }
        }
        double[] minDist = new double[n];
        boolean[] checked = new boolean[n];
        Arrays.fill(minDist, INF);

        minDist[0] = 0;
        PriorityQueue<God> gods = new PriorityQueue<>(Comparator.comparingDouble(g -> g.minDist));
        double totalLength = 0;
        gods.add(new God(0, 0));
        while (!gods.isEmpty()) {
            God curr = gods.poll();
            if (checked[curr.godNo]) continue;
            checked[curr.godNo] = true;
            minDist[curr.godNo] = 0;
            totalLength += curr.minDist;
            for (int i = 0; i < n; i++) {
                if (checked[i]) continue;
                if (minDist[curr.godNo] + dist[curr.godNo][i] < minDist[i]) {
                    minDist[i] = minDist[curr.godNo] + dist[curr.godNo][i];
                    gods.add(new God(i, minDist[i]));
                }
            }
        }
        return totalLength;
    }

    void solution() throws IOException {
        input();
        System.out.printf("%.2f", Prim());
    }

    public static void main(String[] args) throws IOException {
        new BOJ1774().solution();
    }
}