백준 4386번 - 별자리 만들기 (JAVA)

 

문제링크

 

 

문제 풀이 과정

크루스칼 풀이 방법을 그대로 적용하면 되는 문제이다.

크루스칼을 적용하기 전에 한단계 준비 작업이 필요하다. 주어진 데이터는 별들의 좌표만 주어지기 때문에 서로 다른 별들의 거리를 먼저 구한 다음 크루스칼을 적용하면 된다.

 

두점 사이의 거리 구하는 방법이다.

public static double dist (Point p1, Point p2){
    return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}

 

별들의 좌표는 Point class 를 별도로 구현하였다.

 

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

    public Point(double x, double y, int idx) {
        this.x = x;
        this.y = y;
        this.idx = idx;
    }
}

 

거리를 구한 좌표를 관리하기 위해서 Edge class 를 사용하였다.

 

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

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

    @Override
    public int compareTo(Edge o) {
        if(this.v < o.v){
            return -1;
        }
        else{
            return 1;
        }
    }
}

 

 

전체 코드