https://www.acmicpc.net/problem/4386
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
사용 알고리즘: ArrayList, Priority Queue, Union-Find, Kruskal's
먼저, 별의 거리를 저장하는 Edge 클래스를 만들었다. Edge 클래스에서는 시작 정점, 도착 정점, 가중치를 받아준다.
Priority Queue 를 사용하기 위해 compareTo 메서드를 사용해서 가중치를 비교해준다.
import java.util.Scanner;
import java.util.ArrayList;
import java.util.PriorityQueue;
class Edge implements Comparable<Edge> { // 별의 거리를 저장하는 클래스
int u, v; // 시작 정점, 도착 정점
double w; // 가중치
public Edge(int u, int v, double w) {
this.u = u;
this.v = v;
this.w = w;
}
// 가중치가 작은 순으로 정렬
@Override
public int compareTo(Edge other) {
return Double.compare(this.w, other.w);
}
}
Cycle 을 만들지 않기 위해 Union-Find 를 활용해준다.
find 함수는 어떤 원소 a가 주어질 때, 이 원소가 속한 집합을 반환한다.
여기서는 원소 u가 속한 집합의 루트를 찾고 그 루트를 parent[u] 에 다시 넣어준다. 그렇게 해서 path compression 해준다.
path compression 이란?
public class BOJ4386 {
static int[] parent;
public static int find(int u) {
if (parent[u] == u) { // u가 루트인 경우, 자기 자신을 리턴
return u;
}
// path compression 사용
return parent[u] = find(parent[u]); // u가 속한 집합의 루트를 찾는 함수
}
main 함수에서 입출력을 담당한다.
아직 StringTokenizer 가 익숙하지 않아서 시간이 오래걸리는 단점이 있지만 Scanner 로 입력을 받았다.
parent 에 배열을 만들고, 1부터 n 까지 설정해준다. 이 단계에서는 각각 자기 자신이 부모로 설정되어있다.
예를 들어, n = 3 이면 노드 1의 부모는 1이고, 노드 2의 부모는 2고, 노드 3의 부모는 3이다.
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
parent = new int[n+1];
for (int i=1; i<=n; i++) {
parent[i] = i; // 처음에는 자기 자신을 부모로 설정
}
stars 라는 double 타입의 2차 배열을 만들고, 여기에 x 좌표와 y 좌표를 저장해준다.
double[][] stars = new double[n][2];
for (int i=0; i<n; i++) {
stars[i][0] = in.nextDouble(); // x 좌표
stars[i][1] = in.nextDouble(); // y 좌표
}
이제 모든 간선의 리스트를 edges 라는 동적 배열에 저장할 것이다.
두 별 사이의 거리를 계산한 값을 distance 에 추가해준다. 여기 distance 가 가중치가 된다.
i (시작 정점), j (도착 정점), distance (가중치) 의 간선을 Edge 객체로 생성/표현해주고 edges 에 추가한다.
ArrayList<Edge> edges = new ArrayList<>(); // 모든 간선의 리스트
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
// 두 별 사이의 거리 계산
double distance = Math.sqrt(Math.pow(stars[i][0] - stars[j][0], 2) + Math.pow(stars[i][1] - stars[j][1], 2));
edges.add(new Edge(i, j, distance));
}
}
double totalCost = kruskal(edges);
System.out.printf("%.2f", totalCost);
}
Edge 에서 가중치를 비교해놨는데, for 문에서 가중치가 작은 순서대로 정렬한다.
근데 이 부분 다시 봐야할듯? Edge edge 가 뭐지?
public static double kruskal(ArrayList<Edge> edges) {
// 간선들의 가중치를 오름차순으로 저장
PriorityQueue<Edge> pq = new PriorityQueue<>();
for (Edge edge : edges) {
pq.add(edge); // 가중치가 작은 순서대로 정렬
}
pq 에서 가장 큰 것부터 꺼내서 edge 에 저장한다.
시작 정점의 루트를 찾아서 uRoot 에 저장한다.
도착 정점의 루트를 찾아서 vRoot 에 저장한다.
이때, 시작 정점의 루트와 도착 정점의 루트가 같지 않은 경우에만 totalCost 에 가중치를 더해준다.
이후, 부모를 같은 부모로 설정해줌으로서 연결 완료가 된다!
double totalCost = 0; // 최소 비용의 누적 값
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int uRoot = find(edge.u);
int vRoot = find(edge.v);
// 싸이클이 생성되지 않는 경우에만 가중치를 더하고 두 정점을 연결
if (uRoot != vRoot) {
totalCost += edge.w; // 현재 간선의 가중치 더함
parent[uRoot] = vRoot; // uRoot와 vRoot 연결 (부모 갱신)
}
}
return totalCost;
}
}