백준 2887 - 행성 터널
Updated:
Java
2887 번 - 행성 터널
문제
왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
접근 방법
최소 간선 트리를 만드는 문제이므로, prim 알고리즘과 kruscal 알고리즘 중 크루스칼 알고리즘을 이용하였다.
문제의 조건 중 가중치는 min(|xA-xB|, |yA-yB|, |zA-zB|)이라고 했다.
즉, x의 차이 / y의 차이 / z의 차이 중 제일 작은 것만 연결하면 된다는 뜻이다.
행성들간의 x차이, y차이, z차이를 간선의 가중치로 하여, 간선 리스트에 전부 저장하여, 작은 순서부터 크루스칼로 연결하면 MST가 완성된다.
그렇다면 총 (n - 1) * 3의 간선들이 저장된다.
간선을 연결할 때, 한번 x차이가 제일 작은 간선이 연결 되었다면, y차이, z차이인 간선 정보가 연결할려 해도, 행성들은 이미 연결되었으므로 무시된다.
이제, 행성 간에 x, y, z차이를 비교하여야 하는데, 문제의 조건 중 행성 크기는 100,000이다.
즉, 행성 하나를 다른 모든 행성과 비교하기엔 100,000 * 100,000으로 시간초과가 난다.
이를 해결하기 위해, 정렬을 이용하였다.
간단한 예시를 들어, 1차원 상에 1번,2번,3번,…n번 행성이 차례대로 있다고 가정해보면 1번과 2번차이가 제일 작은 연결이 된다.
이 처럼 x, y, z를 각각 기준으로 별들을 정렬한 후, i와 i-1번째의 x, y, z 각각의 차이를 간선에 저장하면, 최소가 된다.
코드
import java.util.*;
import java.io.*;
public class Main {
// ------- 서로소 집합 (disjoint) ------------
static class Edge implements Comparable<Edge>{
int from, to, w;
public Edge(int from, int to, int w) {
super();
this.from = from;
this.to = to;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(w, o.w);
}
}
static void make() {
for(int i = 0; i < n; i++) {
parents[i] = i;
}
}
static int findSet(int a) {
if(parents[a] == a)
return a;
return parents[a] = findSet(parents[a]);
}
static boolean union(int a, int b) {
int aRoot = findSet(a);
int bRoot = findSet(b);
if(aRoot == bRoot)
return false;
int minParents = Math.min(aRoot, bRoot); // 큰 값을 더 작은 값에 넣어 rank를 줄인다.
parents[aRoot] = minParents;
parents[bRoot] = minParents;
return true;
}
// ------- 서로소 집합 끝 ------------
static int n;
static int[] parents;
static ArrayList<Edge> edgeList;
static long result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
n = stoi(br.readLine());
Star[] stars = new Star[n];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
stars[i] = new Star(i, stoi(stk.nextToken()), stoi(stk.nextToken()), stoi(stk.nextToken()));
}
edgeList = new ArrayList<Edge>();
// 행성들의 x 크기 순서대로 정렬 후, 간선 리스트에 저장
Arrays.sort(stars, new Comparator<Star>() {
@Override
public int compare(Star o1, Star o2) {
return Integer.compare(o1.x, o2.x);
}
});
for(int i = 0; i < n - 1; i++)
edgeList.add(new Edge(stars[i].idx, stars[i + 1].idx, Math.abs(stars[i].x - stars[i + 1].x)));
// 행성들의 y 크기 순서대로 정렬, 간선 리스트에 저장
Arrays.sort(stars, new Comparator<Star>() {
@Override
public int compare(Star o1, Star o2) {
return Integer.compare(o1.y, o2.y);
}
});
for(int i = 0; i < n - 1; i++)
edgeList.add(new Edge(stars[i].idx, stars[i + 1].idx, Math.abs(stars[i].y - stars[i + 1].y)));
// 행성들의 z 크기 순서대로 정렬, 간선 리스트에 저장
Arrays.sort(stars, new Comparator<Star>() {
@Override
public int compare(Star o1, Star o2) {
return Integer.compare(o1.z, o2.z);
}
});
for(int i = 0; i < n - 1; i++)
edgeList.add(new Edge(stars[i].idx, stars[i + 1].idx, Math.abs(stars[i].z - stars[i + 1].z)));
// 다시 한번 간선을 오름차순으로 정렬한다.
Collections.sort(edgeList);
parents = new int[n];
make();
int count = 0;
// 크루스칼 알고리즘
for(Edge edge : edgeList) {
if(union(edge.from, edge.to)) {
result += edge.w;
if(++count == n - 1)
break;
}
}
System.out.println(result);
br.close();
}
static class Star{
int idx,x,y,z;
public Star(int idx, int x, int y, int z) {
super();
this.idx = idx;
this.x = x;
this.y = y;
this.z = z;
}
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
간선의 정보는 주어졌으므로, 간선을 queue에 넣어 prim으로도 해결할 수 있다.
개선할 점
없습니다.
