백준 4386 별자리 만들기 java

문제 소개 www.acmicpc.net/problem/4386

내용

• n개의 별들을 이어서 별자리를 하나 만들 것이다.
• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
• 별들이 2차원 평면 위에 놓여 있다.
• 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

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

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

출력

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

해결 방법

아이디어

백준 2887 행성 터널 문제와 마찬가지로 최소 비용 스패닝 트리 문제이다.

백준 2887 행성 터널과 달리 cost가 x축 y축 각각의 값 중 최소값이 아니므로 백준 2887 행성 터널에서 했던 각축으로 정렬 이후 바로 옆에 있는 정점끼리의 간선만 취급해서는 풀리지 않는다.

 

n이 100이다. n^2 해도 10,000 이므로 프림 혹은 크루스칼 알고리즘만 적용하면 풀릴 듯 하다.

크루스칼로 풀어보자.

실제 풀이 코드

package class5.p4386;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 별자리 만들기
 * 2021-01-22
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        List<Star> stars = new ArrayList<>();
        for (int i = 0; i < starsCount; i++) {
            String[] split = br.readLine().split(" ");

            stars.add(new Star(i, Double.parseDouble(split[0]), Double.parseDouble(split[1])));
        }

        List<Edge> edges = new ArrayList<>();
        for (Star from : stars) {
            for (Star to : stars) {
                edges.add(new Edge(from.index, to.index, from.calcCost(to)));
            }
        }

        Collections.sort(edges);

        int[] cycleTable = new int[starsCount];

        for (int i = 0; i < starsCount; i++) {
            cycleTable[i] = i;
        }

        double answer = 0.0;
        for (Edge edge : edges) {
            int fromParent = getParent(cycleTable, edge.from);
            int toParent = getParent(cycleTable, edge.to);

            if (fromParent != toParent){
                union(cycleTable, fromParent, toParent);
                answer += edge.cost;
            }
        }

        System.out.printf("%.2f", answer);
    }

    private static void union(int[] cycleTable, int from, int to) {
        int fromParent = getParent(cycleTable, from);
        int toParent = getParent(cycleTable, to);
        if (fromParent > toParent) cycleTable[fromParent] = toParent;
        else cycleTable[toParent] = fromParent;
    }

    private static int getParent(int[] cycleTable, int from) {
        if (cycleTable[from] == from) return from;
        return getParent(cycleTable, cycleTable[from]);
    }

    static class Star {
        int index;
        double x;
        double y;

        public Star(int index, double x, double y) {
            this.index = index;
            this.x = x;
            this.y = y;
        }

        public double calcCost(Star other) {
            return Math.sqrt(Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2));
        }
    }

    static class Edge implements Comparable<Edge>{
        int from;
        int to;
        double cost;

        public Edge(int from, int to, double cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

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

결과