백준 4386 (별자리 만들기) - java

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

4386번: 별자리 만들기

간선에 대한 정보가 주어지지 않지만 MST 문제이다. 맘대로 간선을 만들 수 있기 때문에 가능한 모든 간선에 대하여 경우를 생각하면 된다.

 

java에서 우선순위 큐를 사용할 때 비교 대상으로 Double 타입 지정시 !

 PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) ->  Double.compare(x.cost , y.cost) // 우선순위 큐 : 비용을 중심
        );

• Double,compare(x,y) 를 사용하면 된다 !

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

public class Main {
    static int n = 0;
    static int[] root;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        root = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            root[i] = i; // 초기화
        }

        star[] arr = new star[n+1];

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            double x = Double.parseDouble(st.nextToken());
            double y =  Double.parseDouble(st.nextToken());
            star cur = new star(x,y);

            arr[i] = cur; // 별의 좌표 저장
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) ->  Double.compare(x.cost , y.cost) // 우선순위 큐 : 비용을 중심
        );

        for(int i=1;i<n;i++)
        {
            for(int j= i+1;j<=n;j++)
            {
                Edge edge = new Edge(i,j,cal(arr[i], arr[j])); // 간선에 대한 정보 저장

                pq.add(edge);
            }
        }

        double re = 0.0;
        while(!pq.isEmpty()) {
            Edge cur = pq.poll();

            if (find(cur.x) != find(cur.y))
            {
                re += cur.cost;
                union(cur.x ,cur.y); // 크루스컬 알고리즘
            }
        }

        System.out.printf("%.2f",re);
        System.out.println();
        br.close();
    }



    static int find(int x)
    {
        if(x == root[x])
            return x;
        else{
            return root[x] = find(root[x]);
        }
    }

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

        if(x < y)
            root[y] = x;

        else
            root[x] = y;
    }

    static double cal(star cur1 , star cur2)
    {
        double tmp1 = Math.pow((cur1.x - cur2.x),2);
        double tmp2 = Math.pow((cur1.y - cur2.y),2);

        return Math.sqrt(Math.abs(tmp2 + tmp1)); // 별 사이 거리 계산
    }
}
class star
{
    double x;
    double y;

    star(double x,double y)
    {
        this.x = x;
        this.y = y;
    }
}

class Edge
{
    int x;
    int y;
    double cost;

    Edge(int x,int y, double cost)
    {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
}