[백준] 4386번 : 별자리 만들기

4386번: 별자리 만들기

# 문제

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

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

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

# 입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

# 출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

# 예제 입력

3

1.0 1.0

2.0 2.0

2.0 4.0

# 예제 출력

3.41

---

[크루스칼(Kruskal) 알고리즘을 이용한 최소 신장 트리(Minimum Spanning Tree, MST)]

각 점(x, y)를 저장해놓고 1, 2, 3, ... n 점에 대해 모든 점마다 간선을 생성한다. 간선은 home과 target, 그리고 가중치 dist를 갖는다.

 

모든 간선을 List에 담고 오름차순 정렬 후 크루스칼 알고리즘을 사용해 MST의 값을 소수 둘째자리 까지 쓰면 된다.

 

필자는 (x1, y1) --> (x2, y2), (x3, y3), ..., (xn, yn) 모든 점에 대해 간선을 생성하지 않고 x1, y1 -> x2, y2   x2, y2 -> x3, y3 같이 i번째와 i+1번째에 대해서만 간선을 생성하는 큰 실수를 범했었다.

# Code </>

public class Main {
    static class Point{
        double y, x;
        public Point(double yy, double xx){
            y=yy; x=xx;
        }
    }
    
    static class Edge implements Comparable<Edge>{
        double d;
        int h, tg;
        public Edge(int home, int t, double dist){
            h=home; tg=t; d=dist;
        }

        @Override
        public int compareTo(Edge o) {
            if(d > o.d) return 1;
            else if(d < o.d) return -1;
            return 0;
        }
    }
    static final int N = 102;
    static int n;

    static Point[] v = new Point[N];
    static List<Edge> list = new ArrayList<>();

    /* Union-Find */
    static int[] parent = new int[N];
    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);
        return a == b?true:false;
    }
    static void unionParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(a > b) parent[a] = b;
        else parent[b] = a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());

            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());

            v[i] = new Point(y, x);
            parent[i] = i;
        }

        //모든 점에 대해 간선 생성
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i != j)
                    list.add(new Edge(i, j, Math.sqrt( Math.pow((v[i].y - v[j].y), 2) + Math.pow((v[i].x - v[j].x), 2) )));

        Collections.sort(list);

        double sum = 0.0;
        
        for(Edge edge:list)
            if(!findParent(edge.h, edge.tg)){
            
                sum += edge.d;
                unionParent(edge.h, edge.tg);
            }
            
        System.out.println(Math.round(sum * 100)/100.0);
    }
}