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

백준🔗

4386번: 별자리 만들기

 

문제

 

 

간단 풀이

별들을 최소 비용으로 모두 잇는 문제이기 때문에 최소 스패닝 트리(MST)로 생각하고 접근하면 된다.

 

다만, 간선이 미리 주어지는 것이 아니라 어떤 정점이든 모두 이을 수 있다는 것이 이전에 풀었던 문제들과 다른 포인트인 것 같다.

따라서 크루스칼과 프림 중 프림 방식을 선택했다. 이전 포스팅

(👉 2023.06.16 - [알고리즘/백준] - [백준/JAVA] 1197_최소 스패닝 트리)

에서도 얘기했듯이 크루스칼은 최소 비용의 '간선'을 선택하는 것이기 때문에 시작 단계에서 모든 간선을 가중치에 따라 오름차순으로 정렬해 둔 뒤에 사이클이 생기지 않도록 선택해 나가게 되는데, 이 문제에서는 가능한 간선의 개수가 n*(n+1)/2개로 정점 개수에 비해 너무 많기 때문에 크루스칼보다 프림이 더 효율적이라고 생각했기 때문이다.

 

따라서 프림을 우선순위 큐를 사용해서 구현했다. 

1) 임의의 정점을 하나 선택해서 시작한다.

2) 아직 방문하지 않은 정점들 중 최소 비용의 간선이 존재하는 '정점'을 선택한다.

3) 해당 정점에서 갈 수 있는 미방문 정점들을 우선순위 큐에 넣는다.

4) 모든 정점이 선택될 때까지 2, 3번 과정을 반복한다.

 

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 별 개수
		double[][] star = new double[n][2];
		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());
		}

		boolean[] visited = new boolean[n];
		PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				if (o1.d > o2.d) {
					return 1;
				} else {
					return -1;
				}
			}
		});
		// 시작 정점 뽑기
		visited[0] = true;
		for (int i = 1; i < n; i++) {
			pq.add(new Edge(0, i, getDistance(star[0][0], star[0][1], star[i][0], star[i][1])));
		}
		int pick = 1;
		double cost = 0;
		while (pick != n) {
			Edge cur = pq.poll();
			if (visited[cur.ed])
				continue;
			visited[cur.ed] = true;
			pick++;
			cost += cur.d;
			for (int i = 1; i < n; i++) {
				if (!visited[i]) {
					pq.add(new Edge(cur.ed, i, getDistance(star[cur.ed][0], star[cur.ed][1], star[i][0], star[i][1])));
				}
			}
		}
		System.out.println(Math.floor(cost * 100) / 100.00);
	}

	static double getDistance(double x1, double y1, double x2, double y2) {
		return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
	}

	static class Edge {
		int st, ed;
		double d;

		public Edge(int st, int ed, double d) {
			this.st = st;
			this.ed = ed;
			this.d = d;
		}
	}
}

 

참고 자료