[백준] 4386 별자리 만들기 - Java

 

 

문제 출저 

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

4386번: 별자리 만들기

 

 

 

문제 풀이 

별들의 좌표가 주어진다. 별들의 거리는 직각 삼각형 공식으로 구할 수 있다. 이 때, 모든 별들을 연결했을 때 가장 적은 거리가 무엇인지 구해야한다. 

 

이 문제는 최소 스패닝 트리로 크루스칼 알고리즘으로 풀었다. 

먼저 PriorityQueue<dot> pq를 선언하였다. 이 PriorityQueue는 두 별의 거리를 저장하는 용으로 거리를 오름차순으로 정렬했다. dot에는 int s, int e, double cost가 있어 연결된 두 별(s,e)와 거리(cost)를 저장했다. 

Union - find를 만들고 연결 정보를 나타내는 int[] parents 을 선언했다.

pq에서 가장 거리가 짧은 순으로 가져와 find를 통해 부모를 찾아서 부모가 다르면 union을 통해 연결시켜주고 그 비용을 더해 정답을 구했다. 

모두 연결되어있는 것은 모든 별자리 번호를 탐색하여 find()로 부모가 같은지를 확인했다. 

 

 

 

소스 코드 

package baekjoon.backjoon9.day11;

/*
별자리 만들기
https://www.acmicpc.net/problem/4386
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class B4386 {

    static int n;
    static double[][] board;
    static PriorityQueue<dot> pq;

    static int[] parents;



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new double[n][2];

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            board[i][0] = Double.parseDouble(st.nextToken());
            board[i][1] = Double.parseDouble(st.nextToken());
        }

        pq = new PriorityQueue<>();
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                double distance = Math.sqrt(Math.pow(board[i][0] - board[j][0], 2) + Math.pow(board[i][1] - board[j][1], 2));
                pq.add(new dot(i, j, distance));
            }
        }

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

        double answer = 0.0;

        while (!pq.isEmpty()) {
            dot d = pq.poll();

            if(find(d.s) != find(d.e)) {
                answer += d.cost;
                union(d.s, d.e);

                if(check()) {
                    break;
                }
            }
        }

        System.out.println(String.format("%.2f", answer));

    }

    public static boolean check() {
        for(int i = 0; i < n; i++) {
            if(find(0) != find(i)) {
                return false;
            }
        }
        return true;
    }

    public static int find(int x) {
        if(parents[x] == x) {
            return x;
        }

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

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x > y) {
            parents[x] = y;
        }
        else {
            parents[y] = x;
        }

    }

    public static class dot implements Comparable<dot> {
        int s;
        int e;
        double cost;

        dot(int s, int e, double cost) {
            this.s = s;
            this.e = e;
            this.cost = cost;
        }

        public int compareTo(dot d) {
            if(this.cost < d.cost) {
                return -1; // 현재객체가 매개변수 객체보다 앞에 위치해야함
            }
            if(this.cost > d.cost) {
                return 1; // 현재객체가 매개변수객체보다 뒤에 위치해야함
            }
            return 0;

        }
    }

}