[BOJ] 백준 4386 : 별자리 만들기 (java)

🧪 4386 별자리 만들기

---

난이도 : 🌟 골드 3
유형 : 크루스칼

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

 

📝 문제

---

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

 

- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.

- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

 

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

 

입력

 

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

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

 

출력

 

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

 

🧐 핵심 로직 

---

1. fillGraph() 메서드를 통해 각 정점의 좌표 정보를 입력받고, Graph 객체 배열에 저장한다.

 

2. connectNodes() 메서드를 이용해 모든 정점 쌍 사이의 거리를 계산한 후, 이를 Edge 객체로 표현하여 리스트에 저장한다. 거리 계산은 유클리드 거리를 사용한다.

 

3. kruskal() 메서드에서 크루스칼 알고리즘을 적용하여 최소 스패닝 트리를 만든다. 이를 위해 간선 리스트를 거리 기준으로 오름차순 정렬한 후, 사이클 방지를 위해 유니온-파인드(Union-Find) 알고리즘의 find와 union 연산을 사용한다.

 

4. 간선을 선택할 때마다 두 정점이 서로 다른 집합에 속해 있는 경우에만 합치고, 그 거리를 총 비용(ans)에 더한다.

 

5. 모든 간선을 처리한 후, 최소 스패닝 트리의 총 거리를 출력한다.

 

💻 최종 코드 (116 ms)

---

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

public class Main {

    static class Graph {

        int idx;
        double x, y;

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

    static class Edge implements Comparable<Edge> {

        int start, end;
        double dis;

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

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

    static BufferedReader br;
    static int n;
    static double ans;
    static Graph[] graphs;
    static List<Edge> edges;
    static int[] parent;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));

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

        fillGraph();
        connectNodes();

        ans = 0;
        kruskal();

        System.out.println(ans);

        br.close();
    }

    private static void fillGraph() throws Exception {

        graphs = new Graph[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());

            graphs[i] = new Graph(i, x, y);
        }
    }

    private static void connectNodes() {

        edges = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double dis = calculateDis(graphs[i], graphs[j]);

                edges.add(new Edge(graphs[i].idx, graphs[j].idx, dis));
            }
        }
    }

    private static void kruskal() {

        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        Collections.sort(edges);

        for (Edge edge : edges) {
            if (find(edge.start) != find(edge.end)) {
                union(edge.start, edge.end);
                ans += edge.dis;
            }
        }
    }

    private static double calculateDis(Graph g1, Graph g2) {
        return Math.sqrt(Math.pow((g1.x - g2.x), 2) + Math.pow((g1.y - g2.y), 2));
    }

    private static void union(int x, int y) {

        x = find(x);
        y = find(y);

        if (y != x) {
            parent[y] = x;
        }
    }

    private static int find(int x) {

        if (x == parent[x]) {
            return x;
        }

        return parent[x] = find(parent[x]);
    }
}