[백준/JAVA] BOJ 4386 - 별자리 만들기

오랜만에 최소 신장 트리 문제를 풀어 보았다

👀 문제

4386번: 별자리 만들기 ✨ 골드 3

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

예제 입력

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력

3.41

🔑 키포인트

최소 신장 트리

✍️ 코드

📍 개인적으로 프림 알고리즘을 좋아해서 해당 방식으로 풀었다!
💡 2차원이므로 거리 계산하는 공식은 Math .sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2))

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

public class BOJ4386_별자리만들기 {
    static int n;
    static double answer;
    static boolean[] visited;
    static PriorityQueue<Node> pq;
    static ArrayList<ArrayList<Node>> arr;

    static class Node implements Comparable<Node> {
        int idx;
        double dist;

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

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

    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());
        double[][] point = new double[n][2];
        arr = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            arr.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            point[i][0] = Double.parseDouble(st.nextToken());
            point[i][1] = Double.parseDouble(st.nextToken());
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (i != j) {
                    double dis = Math
                            .sqrt(Math.pow(point[i][0] - point[j][0], 2) + Math.pow(point[i][1] - point[j][1], 2));
                    arr.get(i).add(new Node(j, dis));
                    arr.get(j).add(new Node(i, dis));
                }
            }
        }

        visited = new boolean[n];
        pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0));
        connect();
        System.out.printf("%.2f\n", answer);
    }

    static void connect() {
        int cnt = 0;
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            if (!visited[now.idx]) {
                visited[now.idx] = true;
                answer += now.dist;

                if (++cnt == n) {
                    break;
                }

                for (Node next : arr.get(now.idx)) {
                    if (!visited[next.idx]) {
                        pq.offer(next);
                    }
                }
            }
        }
    }
}