[백준] 4386 : 별자리 만들기 - JAVA

🙋🏻‍♀️ 프림알고리즘 이용!

문제 분석

이 문제는 특정 간선들의 정보를 주는게아니라, 각 별들의 위치를 주기떄문에 결국 모든 별들이 다 직접적으로 연결되어있다고 가정하고 푸는거나 마찬가지이다.

제출코드

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

class Edges implements Comparable<Edges> {
	int w;
	double cost;
	
	Edges(int w, double cost) {
		this.w = w;
		this.cost = cost;
	}
	
	@Override
	public int compareTo(Edges o) {
		if (this.cost > o.cost) {
            return 1;
        } else if(this.cost < o.cost)  {
            return -1;
        } else {
            return 0;
        }
	}
}

public class Main {
static List<Edges>[] graph;
	public static void prim(int start, int n) {
		boolean[] visited = new boolean[n+1];
		PriorityQueue<Edges> pq = new PriorityQueue<>();
		double total=0;
		pq.offer(new Edges(start,0.0));
		
		while(!pq.isEmpty()) {
			Edges edge = pq.poll();
			int v = edge.w;
			double cost = edge.cost;
			if(visited[v]) continue;
			visited[v] = true;
			total += cost;
			for(Edges e : graph[v]) {
				pq.offer(e);
			}
		}
		System.out.printf("%.2f",total);
	}
	
	public static double getDistance(double x, double y) {
		return Math.sqrt(x + y);
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		double[][] location = new double[n+1][2];
		graph = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			graph[i] = new ArrayList<>();
		}
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			double x = Double.parseDouble(st.nextToken());
			double y = Double.parseDouble(st.nextToken());
			
			location[i][0] = x;
			location[i][1] = y;
		}
		for(int i=1; i<n ;i++) {
			for(int j=i+1; j<=n; j++) {
				double xPow = Math.pow(location[i][0]-location[j][0],2);
				double yPow = Math.pow(location[i][1]-location[j][1],2);
				double dis = getDistance(xPow,yPow);
				graph[i].add(new Edges(j,dis));
				graph[j].add(new Edges(i,dis));
			}
		}
		prim(1,n);
	}
}

궁금한 점

graph[i].add(new Edges(j,dis));
graph[j].add(new Edges(i,dis));

꼭 이렇게 양방향으로 그래프에 정보를 다 넣어야할까?
그럼 우선순위큐에 들어가는 정보가 너무 많아질텐데..

공부한 사항

절대/상대 오차는 10^(-2)까지 허용한다.
-> 이 문구에 대한 정확한 의미가 처음에 헷갈렸다. 내 추측으로 풀어서 맞긴했는데, 정확한 의미를 알기위해 공부한다.

정답이 정확히 X일 경우, X-0.01 이상 X+0.01 이하인 임의의 실수를 출력하면 정답으로 인정된다는 뜻이다.