[백준] 4386번: 별자리 만들기 Java
문제
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10^(-2)까지 허용한다.
https://www.acmicpc.net/problem/4386
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
접근
최소 신장 트리(MST, Minimum Spanning Tree) 문제이다.
신장트리(스피닝 트리)란 여러개의 간선 중 일부 간선만을 선택해 트리를 구성하는 것으로,
최소 신장 트리는 간선 간의 가중치의 합이 가장 적은 신장 트리이다.
이를 정리하면 3가지 조건을 가져야 한다.
1) 간선의 가중치의 합이 최소이어야 한다. (최소 신장 트리)
2) 간선의 개수는 n-1이어야 한다. (최소 신장 트리)
3) 싸이클이 존재하지 않아야 한다. (최소 신장 트리)
이를 해결하는 방법은 크게 2가지 알고리즘 방법이 존재한다.
1. Kruskal MST 알고리즘
2. Prim MST 알고리즘
이번엔 Prim MST 알고리즘으로 문제를 해결하겠다.
Prim MST 알고리즘은 한 노드에서부터 점점 트리를 확장해나가는 방법으로
한 간선이 아닌 트리와 연결된 간선 중 가장 작은 가중치의 간선을 택한다.
1) 한 노드와 연결된 간선 정보를 간선 리스트에 추가한다.
2) 간선 리스트 중 연결된 다른 노드가 아직 선택되지 않았고 가장 가중치가 작은 간선을 선택한다.
3) 선택한 간선에 대해 1)~3) 과정을 반복한다.
4) 선택한 간선의 개수가 노드의 개수 -1 이면 종료한다.
별들은 2차원 좌표값(x,y)으로 정보가 주어진다.
별 하나를 선택하여 다른 별들과의 거리와 다른 별의 정보를 가진 edge클래스를 생성하여
거리가 작을수록 먼저 poll되는 우선순위 큐에 집어넣는다.
우선순위 큐에서는
아직 별자리에 들어가지 않은 별이라면 (방문하지 않은 별이라면)
별자리에 포함시키고, 다시 재탐색한다.
만약 별자리 간선의 개수가 별개수 -1 이라면 종료시킨다.
구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
//https://www.acmicpc.net/problem/4386
static int N;
static List<Star> Stars;
static boolean[] Visited;
//별의 좌표를 저장할 클래스
static class Star {
double x,y;
//생성자
public Star(double x, double y) {
this.x=x;
this.y=y;
}
//별끼리 거리의 제곱 계산
public double getPowDistance(Star star) {
return Math.pow(this.x-star.x, 2)+ Math.pow(this.y-star.y, 2);
}
//별끼리 거리 계산
public double getDistance(Star star) {
return Math.sqrt(getPowDistance(star));
}
}
//별의 거리를 저장할 클래스
static class Edge implements Comparable<Edge>{
//도착지점의 별 번호
int n;
//별 트리와의 거리
double val;
//생성자
public Edge(int n, double val) {
this.n = n;
this.val = val;
}
//pq의 우선순위를 위한 compareTo 오버라이드, 거리가 짧은 순
@Override
public int compareTo(Edge o) {
if(this.val<o.val) return -1;
if(this.val>o.val) return 1;
return 0;
}
}
//prim MST 알고리즘
public static double primMst(int starNo) {
//트리와의 거리를 기록할 pq, 거리가 짧은 순서가 먼저 poll
PriorityQueue<Edge> pq = new PriorityQueue<>();
//너비 우선 탐색을 위한 큐
Queue<Integer> q = new LinkedList<>();
//시작점 큐에 추가
q.add(starNo);
//edge의 개수 측정을 위한 선언, 트리의 edge는 N-1개
int edgeCount = 0;
//모든 거리의 합을 위한 sum 선언
double sum = 0d;
//현재 좌표를 저장할 Star 객체 선언
Star star;
//도착지점과 거리를 저장할 Edge 객체 선언
Edge e;
//너비 우선 탐색
while(!q.isEmpty()) {
//현재 위치하는 별
int curr = q.poll();
//방문 여부 표시(트리 추가됨을 표시함)
Visited[curr]=true;
//스타 객체가져오기
star = Stars.get(curr);
//다른 별들과의 거리 탐색
for(int i=0;i<N;i++) {
//이미 방문(트리를 구성)하지 않는다면
if(!Visited[i]) {
//pq에 Edge 객체 추가(도착별, 거리)
pq.add(new Edge(i, star.getDistance(Stars.get(i))));
}
}
//pq 탐색
while(!pq.isEmpty()) {
//엣지 객체
e =pq.poll();
//트리를 구성하지 않았다면
if(!Visited[e.n]) {
//답 업데이트
sum+=e.val;
//큐에 삽입하여 탐색
q.add(e.n);
//엣지 개수 증가
edgeCount++;
//pq 탐색 중지
break;
}
}
//간선 개수가 N-1이면 트리가 완성되었음으로 중지
if(edgeCount==N-1) break;
}
//간선들의 합 출력
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); //별의 개수
Stars = new ArrayList<>(); //별의 좌표를 넣을 리스트
Visited = new boolean[N]; //방문 여부(트리 구성 여부) 표시
StringTokenizer st;
for(int i=0;i<N;i++) {
st=new StringTokenizer(br.readLine());
double x=Double.parseDouble(st.nextToken());
double y=Double.parseDouble(st.nextToken());
Stars.add(new Star(x,y)); //별의 좌표 추가
}
//프림 알고리즘으로 MST 출력
System.out.println(primMst(0));
br.close();
}
}