백준 4386 - 별자리 만들기

Java

4386번 - 별자리 만들기

문제

아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
  별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

접근 방법

1. 별 사이의 거리를 2차원 배열로 전부 얻는다.
2. MST(최소 신장 트리)를 만들어, 그 값을 결과로 출력한다.

소수점 2자리까지 출력해야하므로, Math.round()를 사용하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	double[][] star = new double[n][2];
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		star[i][0] = Double.parseDouble(stk.nextToken());
    		star[i][1] = Double.parseDouble(stk.nextToken());
    	}
		// 별 사이의 거리를 계산
    	double[][] dis = new double[n][n];
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < n; j++) {
    			if(i == j) 
    				continue;
    			dis[i][j] = Math.sqrt(Math.pow(star[i][0] - star[j][0] , 2) +  Math.pow(star[i][1] - star[j][1] , 2));
    		}
    	}
    	
		// MST를 만든다.
    	double[] minEdge = new double[n];
    	Arrays.fill(minEdge, Double.MAX_VALUE);
    	boolean[] vis = new boolean[n];
    	int curV = 0;
    	double min, result = 0;
    	minEdge[0] = 0.0;
    	for(int c = 0; c < n; c++) {
    		min = Double.MAX_VALUE;
    		
    		for(int i = 0; i < n; i++) {
    			if(!vis[i] && min > minEdge[i]) {
    				min = minEdge[i];
    				curV = i;
    			}
    		}
    		
    		result += min;
    		vis[curV] = true;
    		
    		for(int i = 0; i < n; i++) {
    			if(!vis[i] && dis[curV][i] != 0 && minEdge[i] > dis[curV][i]) {
    				minEdge[i] = dis[curV][i];
    			}
    		}
    	}
    	
    	// 소수점 2자리까지 반올림
    	System.out.println(Math.round(result*100) / 100.0);
    	
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

MST의 복습

개선할 점

없습니다.