[백준] 4386번. 별자리 만들기(JAVA)

문제

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

---

풀이(43분)

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static ArrayList<Edge> edges = new ArrayList<>();
    static ArrayList<Point> points = new ArrayList<>();
    static int[] parent;

    public static class Edge implements Comparable<Edge>{
        int start;
        int end;
        double distance;

        public Edge(int start, int end, double distance){
            this.start = start;
            this.end = end;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge other) {
            return Double.compare(this.distance, other.distance);
        }

    }

    public static class Point{
        int num;
        double x;
        double y;

        public Point(int num, double x, double y){
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        parent = new int[n];

        int count = 0;
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            points.add(new Point(i,x,y));
            parent[i] = i;
            for(int j = 0; j < i; j++){
                double distance = distanceCalculator(points.get(i), points.get(j));
                edges.add(new Edge(i,j,distance));
            }
        }

        Collections.sort(edges);
        double answer = 0;

        for(int i = 0; i < edges.size(); i++){
            Edge edge = edges.get(i);
            Point startPoint = points.get(edge.start);
            Point endPoint = points.get(edge.end);
            if(find(parent[startPoint.num]) != find(parent[endPoint.num])){
                union(startPoint.num, endPoint.num);
                answer += edge.distance;
            }
        }

        System.out.println(answer);
    }

    public static double distanceCalculator(Point firstPoint, Point secondPoint){
        double distance = Math.sqrt(Math.pow((firstPoint.x - secondPoint.x), 2) + Math.pow((firstPoint.y - secondPoint.y), 2));
        return Math.round(distance * 100)/100.0;
    }

    // Union 연산
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) { // 이미 같은 집합이 아닐 때만 병합
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }

    // Find 연산 (경로 압축 포함)
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }


}

 

n이 최대 100이기 때문에 MST를 직접 전부 계산하였다.

그 과정 속에서 Union-Find 연산을 적용하였다.

 

풀이 과정은 다음과 같다.

1. 모든 정점을 연결한 간선을 만든다.(100개의 정점을 연결한 것이기 때문에 시간 상 문제가 안 생길 것이다.)

2. 이를 정렬한다.

3. union-find와 mst를 적용해가며 최소 신장 트리를 구현한다.