BOJ 4386 별자리

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

4386번: 별자리 만들기

 

MST를 구하는 문제,

각 별자리 좌표간의 값을 Edge로 넣고 MST를 구하면 됨.

n의 개수가 1 ≤ n ≤ 100 인상태라..

그냥 구하면 됨

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

public class BOJ4386 {
    static int N;
    static Pos[] spos;
    static ArrayList<Edge> edges;
    static DJS djs;
    static class Pos {
        double x, y;
        Pos(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    static class Edge implements Comparable<Edge> {
        int s, e;
        double v;
        Edge(int s, int e, double v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }

        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.v, o.v);
        }
    }
    static double dist(Pos A, Pos B) {
        return Math.sqrt(Math.pow((A.x-B.x),2) + Math.pow((A.y-B.y),2));
    }
    static class DJS{
        int[] mom;
        DJS(int n){
            mom = new int[n+1];
            for (int i = 1; i <=n ; i++) mom[i] = i;
        }
        int find(int n) {
            if(n==mom[n]) return n;
            return mom[n] = find(mom[n]);
        }
        boolean union(int a, int b) {
            a = find(a);
            b = find(b);
            if(a==b) return false;
            mom[b] = a;
            return true;
        }
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/input_boj4386.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        spos = new Pos[N];
        djs = new DJS(N);
        double x, y;
        StringTokenizer st;
        edges = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            x = Double.parseDouble(st.nextToken());
            y = Double.parseDouble(st.nextToken());
            spos[i] = new Pos(x, y);
            for (int j = 0; j < i ; j++) {
                edges.add(new Edge(i,j,dist(spos[i],spos[j])));
            }
        }

        Collections.sort(edges);

        double result = 0;
        for (Edge ed:edges) {
            if(djs.union(ed.s, ed.e)) result += ed.v;
        }

        System.out.println(result);
    }
}