1 분 소요

문제

문제 바로가기

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

접근방법

주어진 별들을 연결하는 MST를 구하는 문제다.

MST 알고리즘은 모든 노드를 연결하면서 그래프의 가중치 합이 최소가 되도록 하는 방법이다.

대표적으로 Kruskal과 Prim이 있다. 이 문제에서는 Prim 알고리즘을 사용하였다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Coo {
    double x, y;
    Coo(double x, double y) {
        this.x = x;
        this.y = y;
    }
}
class Star implements Comparable<Star>{
    int idx;
    double dist;
    Star(int idx, double dist) {
        this.idx = idx;
        this.dist = dist;
    }
    public int compareTo(Star s) {
        return (int)(this.dist - s.dist);
    }
}
public class Main {
    static int N;
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        check = new boolean[N];
        Coo[] coo = new Coo[N];

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            coo[i] = new Coo(Double.parseDouble(st.nextToken()), Double.parseDouble(st.nextToken()));
        }

        List<Star>[] list = new ArrayList[N];
        for(int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                list[i].add(new Star(j, distance(coo[i], coo[j])));
            }
        }

        double res = 0;
        PriorityQueue<Star> pq = new PriorityQueue<>();
        pq.offer(new Star(0, 0));
        while(!pq.isEmpty()) {
            Star tmp = pq.poll();
            if(!check[tmp.idx]) {
                check[tmp.idx] = true;
                res += tmp.dist;
                for (int i = 0; i < list[tmp.idx].size(); i++) {
                    if (!check[list[tmp.idx].get(i).idx]) {
                        pq.offer(list[tmp.idx].get(i));
                    }
                }
            }
        }

        System.out.printf("%.2f", res);
    }

    public static double distance(Coo c1, Coo c2) {
        return Math.sqrt(Math.pow(c1.x - c2.x, 2) + Math.pow(c1.y - c2.y, 2));
    }
}

댓글남기기

참고