백준 4386 - 별자리 만들기

백준 4386 - 별자리 만들기

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

★ 풀이

모든 별을 최소 비용으로 잇는 최소 스패닝 트리(MST) 문제이다. 문제에서는 좌표값만을 주고 있기 때문에 MST를 구현하기 위해 필요한 별 간의 거리는 직접 구해야한다. 나 같은 경우 별들의 좌표값을 따로 저장해 놓은 다음 모든 별 간의 거리를 또 따로 계산해서 MST 구현을 위한 인접 리스트를 만들었다. 이후에는 정형화된 MST 풀이(PRIM)를 통해 답을 구했다.

★ 소스 코드

import java.io.*; import java.util.*; class Point{ double x,y; Point(double x, double y){ this.x = x; this.y = y; } } class Node implements Comparable{ int to; double cost; Node(int to, double cost){ this.to = to; this.cost = cost; } @Override public int compareTo(Node o) { if(this.cost < o.cost) return -1; else if(this.cost == o.cost) return 0; else return 1; } } public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static ArrayList adj[]; static int n; public static void main(String[] args) throws IOException { // 별자리를 만드는 최소 비용을 구해야한다. -> 최소 스패닝 트리 // 2 차원 평면의 거리 n = Integer.parseInt(br.readLine()); Point p[] = new Point[n + 1]; for(int i = 1; i<=n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); double x = Double.parseDouble(st.nextToken()); double y = Double.parseDouble(st.nextToken()); p[i] = new Point(x, y); } adj = new ArrayList[n + 1]; for(int i = 1; i<=n; i++) { adj[i] = new ArrayList<>(); } for(int i = 1; i<=n; i++) { for(int j = 1; j<=n; j++) { if(i == j) continue; double dist = Math.sqrt(Math.pow(Math.abs(p[i].x - p[j].x) , 2) + Math.pow(Math.abs(p[i].y - p[j].y), 2)); adj[i].add(new Node(j,dist)); } } System.out.printf("%.2f",prim()); } static boolean visited[]; static double prim() { visited = new boolean[n + 1]; PriorityQueue pq = new PriorityQueue<>(); pq.add(new Node(1,0)); int cnt = 0; double sum = 0; while(!pq.isEmpty()) { Node x = pq.poll(); if(!visited[x.to]) { visited[x.to] = true; sum += x.cost; if(++cnt == n) return sum; for(Node next : adj[x.to]) { pq.add(next); } } } return -1; } }

from http://sweet-smell.tistory.com/58 by ccl(A) rewrite - 2021-09-27 04:27:47