[BOJ] 백준 1774. 우주신과의 교감

문제

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

 

---

풀이

크루스칼을 이용해 MST를 구하는 문제입니다. 백준의 4386번. 별자리 만들기 문제와 상당히 비슷합니다.

 

 이 문제의 핵심은 좌표(x, y)를 하나의 인덱스로 다루는 것이라고 생각합니다. 좌표를 입력받고, 좌표들을 간선으로 연결할 때에 인덱스를 매겨주며 ArrayList에 추가하고, 간선에 추가된 좌표의 위치는 거리를 구하기 위해서 필요할 뿐이지 더는 필요가 없으므로 시작과 종료 지점의 인덱스로 변환하고 좌표는 버립니다.

 

 그리고 크루스칼 알고리즘을 인덱스로 실행하며 union시에 통로 길이 합을 더해주었습니다.

 

 아래는 소스 코드입니다.

---

소스 코드

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

public class B1774_우주신과의교감 {

    static Scanner sc = new Scanner(System.in);
    static int N,M;
    static int[] parents;
    static ArrayList<int[]> list = new ArrayList<>();
    static ArrayList<Node> edgeList = new ArrayList<>();
    static double ans = 0;

    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){
            return Double.compare(w, o.w);
        }
    }

    public static void main(String[] args) {
        input();
        connect();
        kruskal();
        System.out.printf("%.2f", ans);
    }

    static void kruskal(){
        for(int i = 0; i<edgeList.size();i++){
            int st = edgeList.get(i).st;
            int ed = edgeList.get(i).ed;
            double w = edgeList.get(i).w;
            if(!isParent(st,ed)){
                union(st,ed);
                ans += w;
            }
        }
    }

    static void connect(){
        for(int i =0; i<N-1;i++){
            for(int j = i+1;j<N;j++){
                int[] o1 = list.get(i);
                int[] o2 = list.get(j);
                edgeList.add(new Node(i,j,getDistance(o1,o2)));
            }
        }
        Collections.sort(edgeList);
    }

    static void input(){
        N = sc.nextInt();
        M = sc.nextInt();
        parents = new int[N+1];
        for(int i = 0; i<N+1;i++) parents[i] = i;

        for(int i =0; i<N;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            list.add(new int[]{x,y});
        }
        for(int i = 0; i<M;i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            union(a,b);
        }
    }

    static int findset(int a){
        if(parents[a]!=a) return parents[a]=findset(parents[a]);
        return a;
    }
    static void union(int a, int b){
        a = findset(a);
        b = findset(b);
        if(a!=b){
            parents[b] = a;
        }
    }
    static boolean isParent(int a, int b){
        if(findset(a)!= findset(b)) return false;
        return true;
    }
    static double getDistance(int[] o1, int[] o2){
        int r1 = o1[0];
        int c1 = o1[1];
        int r2 = o2[0];
        int c2 = o2[1];
        return Math.sqrt(Math.pow(r1-r2,2)+Math.pow(c1-c2,2));
    }
}