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

4386 별자리 만들기 사진 클릭시 문제로 이동

---

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다.

별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다.

선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

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

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

좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다.

절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41

---

설명

해당 문제는 다음 알고리즘 분류를 가진다.

• 그래프 이론
• 최소 스패닝 트리

최소 스패닝 트리를 해결하는 알고리즘 중 프림을 이용해 문제를 해결했다.

n개의 별자리의 x좌표와 y좌표가 주어진다.

이때 두 별자리 사이의 거리를 구하기 위해 이중 for문을 사용해 두 점 사이 거리 공식을 이용해 거리를 구한다.

for(int i = 0; i < n; i++) {
	for(int j = i+1; j < n; j++) {
		double x = star[i][0] - star[j][0];
		double y = star[i][1] - star[j][1];
		double len = Math.sqrt((Math.pow(x, 2)+(Math.pow(y, 2))));
		graph[i].add(new edge(j, len));
		graph[j].add(new edge(i, len));
	}
}

거리를 오름차순으로 정렬해 이를 우선순위 큐에 이용한다.

static class edge implements Comparable<edge>{
		int node;
		double weight;
		
		edge(int node, double weight){
			this.node = node;
			this.weight = weight;
		}

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

결과는 소수점 둘째 자리까지 나타내야 함을 잊지 말자

System.out.format("%.2f",result);

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.PriorityQueue;
	import java.util.StringTokenizer;
	public class BOJ4386 {
	static boolean visited[];
	static int count = 0;
	static int n;
	static ArrayList<edge>[] graph;
	static double result = 0;
	static PriorityQueue<edge> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	double star[][] = new double[n][2];
	graph = new ArrayList[n];
	visited = new boolean[n];
	for(int i = 0; i < n; i++) {
	graph[i] = new ArrayList<>();
	}
	for(int i = 0; i < n; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	star[i][0] = Double.parseDouble(st.nextToken());
	star[i][1] = Double.parseDouble(st.nextToken());
	}
	for(int i = 0; i < n; i++) {
	for(int j = i+1; j < n; j++) {
	double x = star[i][0] - star[j][0];
	double y = star[i][1] - star[j][1];
	double len = Math.sqrt((Math.pow(x, 2)+(Math.pow(y, 2))));
	graph[i].add(new edge(j, len));
	graph[j].add(new edge(i, len));
	}
	}
	prim();
	System.out.format("%.2f",result);
	}
	static void prim() {
	pq.add(new edge(0,0));
	while(!pq.isEmpty()) {
	edge cur = pq.poll();
	if(visited[cur.node]) {
	continue;
	}
	visited[cur.node] = true;
	result += cur.weight;
	for(edge next : graph[cur.node]) {
	if(!visited[next.node]) {
	pq.offer(next);
	}
	}
	if(++count == n) {
	break;
	}
	}
	}
	static class edge implements Comparable<edge>{
	int node;
	double weight;
	edge(int node, double weight){
	this.node = node;
	this.weight = weight;
	}
	@Override
	public int compareTo(edge o) {
	if(this.weight < o.weight) {
	return -1;
	}else {
	return 1;
	}
	}
	}
	}

view raw BOJ4386.java hosted with ❤ by GitHub