[백준, BOJ 4386] 별자리 만들기 (java)

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

4386번: 별자리 만들기

728x90

---

메모리: 14,540 KB , 시간: 140  ms

사용 알고리즘: 그래프 이론, 최소 스패닝 트리

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static class Edge implements Comparable {

        int star1;
        int star2;
        double length;

        Edge(int star1, int star2, double length) {
            this.star1 = star1;
            this.star2 = star2;
            this.length = length;
        }

        @Override
        public int compareTo(Object o) {
            Edge other = (Edge)o;

            if(this.length - other.length < 0) return -1;
            else return 1;
        }
    }

    static int[] parent;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

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

        // 모든 별들 사이의 거리 저장
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                edges.add(new Edge(i, j, Math.round(Math.sqrt(Math.pow(point[i][0] - point[j][0], 2) + Math.pow(point[i][1] - point[j][1], 2))*100)/100.0));
            }
        }

        // 별들 사이의 거리 정렬
        Collections.sort(edges);

        // 크루스칼 알고리즘으로 최소 비용으로 모든 별 잇기
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        Edge edge;
        double result = 0;
        for (int i = 0; i < edges.size(); i++) {
            edge = edges.get(i);
            if(union(edge.star1, edge.star2)) result += edge.length;
        }

        System.out.println(result);
    }

    static int find(int a) {
        if(parent[a] == a) return a;

        return parent[a] = find(parent[a]);
    }

    static boolean union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) return false;

        if(a < b) parent[b] = a;
        else parent[a] = b;
        return true;
    }
}