[BOJ] 백준 4386. 별자리 만들기

문제

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

4386번: 별자리 만들기

---

풀이

 전형적인 크루스칼 문제입니다. 가중치 값이 소수라는 것이 조금은 특이합니다.

 

 우선 입력받는 좌표 값을 stars 라는 ArrayList 에 입력받고, 이 값을 edgeList라는 ArrayList에서 연결했습니다.

 

 이 때, 제공되는 좌표를 가중치(거리)로써 필요한 것에 집중하고, 두 쌍의 좌표는 하나의 인덱스(i or j)로 ArrayList에 입력을 해주었습니다. 그렇게 인덱스를 통해 서로 다른 좌표를 연결했습니다.

 

 입력값 N이 최대 100이기 때문에 모든 좌표를 연결해도 시간 범위 안에서 해결할 수 있습니다.

 

아래는 소스 코드입니다.

---

소스코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class B4386_별자리만들기 {
    static Scanner sc = new Scanner(System.in);
    static int N;
    static int[] parents;
    static double ans;
    static class Node implements Comparable<Node>{
        int st;
        int ed;
        double w;
        Node(int st, int ed, double w){
            this.st = st;
            this.ed = ed;
            this.w = w;
        }
        @Override
        public int compareTo(Node o){
            if(w<o.w) return -1;
            return 1;
        }
    }
    static class Point{
        double x;
        double y;
        Point(double x, double y){
            this.x = x;
            this.y = y;
        }
    }
    static ArrayList<Point> stars = new ArrayList<>();
    static ArrayList<Node> edgeList = new ArrayList<>();

    public static void main(String[] args) {
        input();
        connectStar();
        kruskal();
        System.out.println(ans);
    }
    
    static void input(){
        N = sc.nextInt();
        for(int i = 0;i<N;i++){
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            stars.add(new Point(x,y));
        }
    }
    
    
    static void connectStar(){
        for(int i=0;i<N-1;i++){
            for(int j=i+1;j<N;j++){
                Point p1 = stars.get(i);
                Point p2 = stars.get(j);
                edgeList.add(new Node(i,j,getDistance(p1,p2)));
            }
        }
        Collections.sort(edgeList);
    }
    
    static double getDistance(Point p1, Point p2){
        return Math.sqrt(Math.pow(p1.x-p2.x,2)+Math.pow(p1.y-p2.y,2));
    }
    
    
    static void kruskal(){
        initParents();
        for(int i = 0;i<edgeList.size();i++){
            int st = edgeList.get(i).st;
            int ed = edgeList.get(i).ed;
            if(!isParent(st,ed)){
                union(st,ed);
                ans += edgeList.get(i).w;
            }
        }
    }
    
    static void initParents(){
        parents = new int[N+1];
        for(int i =0;i<N+1;i++) parents[i] = i;
    }

    static void union(int x, int y){
        x = findSet(x);
        y = findSet(y);
        if(x!=y) parents[y] = x;
    }
    static int findSet(int x){
        if(x==parents[x]) return x;
        else return parents[x] = findSet(parents[x]);
    }

    static boolean isParent(int x, int y){
        if(findSet(x)==findSet(y)) return true;
        else return false;
    }
}