링크

4386 별자리 만들기

문제

풀이

처음에 이 문제를 접했을 때 거리를 어떻게 구하더라... 까먹었었다.
공식은 피타고라스의 정리를 이용하여 아래와 같다.

최소 스패닝 트리 이 문제와 다르게 거리를 안주어져서 거리값만 구해서 넣어주면 된다.

코드

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

class Node implements Comparable<Node>{
    int node;
    double weight;

    public Node(int node, double weight){
        this.node = node;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o){
        if(this.weight > o.weight){
            return 1;
        } else if(this.weight < o.weight){
            return -1;
        } else{
            return 0;
        }
    }

}


class Star{
    double x;
    double y;

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

public class Algorithm {
    public static boolean[] visited;
    public static List<Node>[] list;
    public static double answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(br.readLine());

        visited = new boolean[n+1];
        list = new List[n+1];

        for(int i=0;i<list.length;i++){
            list[i] = new ArrayList<>();
        }

		//별들의 좌표를 저장할 배열
        Star[] stars = new Star[n+1];
        for(int t=1;t<=n;t++){
            String[] arr = br.readLine().split(" ");
            double starX = Double.parseDouble(arr[0]);
            double starY = Double.parseDouble(arr[1]);

            stars[t] = new Star(starX, starY);
        }

        for(int i=1;i<stars.length;i++){
        	//현재 첫번째 별(A)
            double pivotX = stars[i].x;
            double pivotY = stars[i].y;

            for(int j=i+1;j<stars.length;j++){
            	//A별과 거리를 측정할 B별
                double currentX = stars[j].x;
                double currentY = stars[j].y;
				
                //x와 y좌표 두개 각각 빼서 제곱하기
				//A와 B별의 x좌표 구하기
                double disX = Math.pow(currentX - pivotX, 2);
                //A와 B별의 y좌표 구하기
                double disY = Math.pow(currentY - pivotY, 2);
				
                //루트씌운거를 소수점2자리로 표현하고 Double형으로 변환
                double dis = Double.parseDouble(String.format("%.2f", Math.sqrt(disX + disY)));
                
               	//list에 넣어주기
                list[i].add(new Node(j, dis));
                list[j].add(new Node(i, dis));
            }
        }

        prim(1);
        System.out.println(answer);


    }

	//프림 알고리즘 사용
    public static void prim(int start){
        Queue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node current = pq.poll();
            int to = current.node;
            double weight = current.weight;

            if(visited[to]) continue;

            visited[to] = true;
            answer += weight;

            for(Node element : list[to]){
                if(!visited[element.node]){
                    pq.add(element);
                }
            }

        }

    }
}