[백준 4386] - 별자리 만들기(JAVA)[골드3]

문제

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

4386번: 별자리 만들기

 

문제 풀이

해당 문제는 MST(Minimum Spanning Tree) 알고리즘을 사용하는 문제이다.

왜냐하면 N개의 정점(별)을 이어서 그래프(별)를 만드는데 최소의 비용을 구하라는 문제이기 때문이다.

 

원래 MST의 문제라면 정점간의 간선에 가중치를 입력으로 제공하지만, 해당 문제는 각 좌표를 제공해서,

정점 간의 거리까지 구하는 문제이다.

 

가중치를 제공해주지 않았기 때문에 MST를 제대로 공부하지 않는 사람은 다른 알고리즘으로 착각할만한 여지가 있을 수도 있다.

 

각 정점간의 거리는 수학에서 쓰이는 공식을 사용해서 간단히 구할 수 있다.

이제 정점간의 거리를 모두 구했다면 MST 알고리즘을 이용하면 된다.

 

프림과 크루스칼이 있지만, 이번 문제에서는 크루스칼을 사용했다.

 

그러기 위해서 union & find 함수를 구현하고, 부모 배열을 만들어줬다.

알고리즘의 순서는 이러하다.

 

1. 간선을 오름차순으로 정렬한다.
2. 간선을 선택하고, 부모가 같은지 검사한다.(두 집합이 연결되어 있는지)
   • 연결되어 있다면 간선을 연결하지 않는다.
   • 연결되어 있지 않다면 간선을 연결하고, 부모를 일치시킨다.
3. 1,2번을 반복하다가 모든 정점을 연결했다면(간선의 개수가 n-1)이라면 종료한다.

 

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

public class Main {

    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static double answer = 0;
    static Point[] stars;
    static boolean[] visit;
    static ArrayList<Node> nodes;
    static int[] parent;
    static int cnt;
    public static void main(String[] args) throws IOException {
        input();
        setDistance();
        kruskal();
        answer = Math.round(answer * 100) /100.0;
        System.out.println(answer);
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        stars = new Point[n];
        parent = new int[n];
        nodes = new ArrayList<>();
        double x, y;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            x = Double.parseDouble(st.nextToken());
            y = Double.parseDouble(st.nextToken());
            stars[i] = new Point(i, x, y);
            parent[i] = i;
        }
    }

    public static void setDistance() {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                nodes.add(new Node(i, j, carDistance(stars[i], stars[j])));
            }
        }
        nodes.sort(new Comparator<Node>() {
            @Override
            public int compare(Main.Node o1, Main.Node o2) {
                return (int) (o1.dist - o2.dist);
            }
        });
    }
    public static void union(Node node) {
        int startParent = find(node.from);
        int endParent = find(node.to);

        if(startParent == endParent) //부모가 같으면 연결
            return;
        else if(startParent<endParent) {
            parent[endParent] = startParent;
        } else {
            parent[startParent] = endParent;
        }
        answer+= node.dist;
        cnt++;
    }
    public static int find(int p) {
        if(parent[p]==p)
            return p;
        return parent[p]= find(parent[p]);
    }
    public static void kruskal() {
        for(int i=0;i<nodes.size();i++) {
            if(cnt==n-1)
                break;
            union(nodes.get(i));
        }
    }

    public static double carDistance(Point a, Point b) {

        double distance = Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
        return distance;
    }

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

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

    static class Node {
        int from, to;
        double dist;

        public Node(int from, int to, double dist) {
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
    }
}