백준 4386 별자리 만들기 [자바]

08 Jun 2022 in Develop / Solving

baekjoon 4386 별자리 만들기

java

문제 분석

• 별들의 좌표가 양의 실수로 주어진다.
• 모든 별을 이으면서, 선분의 길이의 합이 최소가 되는 별자리의 선분의 길이를 구해라.

입력조건

별의 개수 N
N줄에 걸쳐서 {
	별자리의 좌표 x, y
}

풀이과정

• 최소 스패닝 트리
• 주어지는 별들에 번호를 매기고, 모든 별에서 별로 가는 길이를 구해서 간선 배열로 만듬.
• 이 간선 배열을 이용하여,
  크루스칼 알고리즘으로 최소 스패닝 트리를 구함.

코드 구성

• 서로소 집합(유니온 파인드)

  public static int parent(int x) {
      if(p[x] == x) return x;
      else return p[x] = parent(p[x]);
  }
  public static void union(int x, int y) {
      p[parent(y)] = parent(x);
  }
  

• 크루스칼 알고리즘

  p = new int[N];
  for(int i = 0; i < N; i++) p[i] = i;
    
  int selected = 0;
  double cost = 0;
  while(selected < N-1) {
      vertex now = pq.poll();
    
      if(parent(now.u) == parent(now.v)) continue;
    
      selected++;
      cost += now.w;
      union(now.u, now.v);
  }
  

• 입력받은 좌표를 이용하여, 간선 구해놓기.

  double[][] map = new double[N][2];
  for(int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      map[i][0] = Double.parseDouble(st.nextToken());
      map[i][1] = Double.parseDouble(st.nextToken());
  }
  // 입력 완료
    
  PriorityQueue<vertex> pq = new PriorityQueue<>();
  for(int i = 0; i < N; i++) {
      for(int j = i+1; j < N; j++) {
          double dist = Math.sqrt(Math.pow(map[i][0] - map[j][0], 2) + Math.pow(map[i][1] - map[j][1], 2));
          pq.add(new vertex(i, j, dist));
      }
  }
  // 자료 정리 완료
  

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ4386_별자리만들기 {
	static int[] p;
	static class vertex implements Comparable<vertex> {
		int u, v;
		double w;
		vertex(int u, int v, double w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo(vertex o) {
			return Double.compare(this.w, o.w);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		double[][] map = new double[N][2];
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			map[i][0] = Double.parseDouble(st.nextToken());
			map[i][1] = Double.parseDouble(st.nextToken());
		}
		// 입력 완료
		
		PriorityQueue<vertex> pq = new PriorityQueue<>();
		for(int i = 0; i < N; i++) {
			for(int j = i+1; j < N; j++) {
				double dist = Math.sqrt(Math.pow(map[i][0] - map[j][0], 2) + Math.pow(map[i][1] - map[j][1], 2));
				pq.add(new vertex(i, j, dist));
			}
		}
		// 자료 정리 완료
		
		p = new int[N];
		for(int i = 0; i < N; i++) p[i] = i;
		
		int selected = 0;
		double cost = 0;
		while(selected < N-1) {
			vertex now = pq.poll();
			
			if(parent(now.u) == parent(now.v)) continue;
			
			selected++;
			cost += now.w;
			union(now.u, now.v);
		}
		System.out.printf("%.2f", cost);
	}
	public static int parent(int x) {
		if(p[x] == x) return x;
		else return p[x] = parent(p[x]);
	}
	public static void union(int x, int y) {
		p[parent(y)] = parent(x);
	}
}