설명
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
예시 입력
예시 출력
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
JavaScript
복사
4
JavaScript
복사
풀이 과정
문제에서 요구하는 건 다음과 같습니다
모든 행성을 터널로 연결하는데 필요한 최소 비용
행성을 정점이라고 생각하고, 터널을 간선이라고 생각한다면 그래프의 모든 정점을 연결하는 그래프 중에서 그 가중치의 합이 최소인 최소 스패닝 트리를 생각할 수 있습니다.
최소 스패닝 트리를 구하기 위해서는 총 두 개의 함수가 필요합니다. (우린 이걸 국룰 함수라고 부르기로 했습니다)
public static int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
public static void union(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
parent[y] = x;
}
}
C
복사
최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 구할 수 있는데, 간단히 설명하자면 간선의 가중치가 작은 순으로 정점과 정점을 연결하는데 이 때 사이클을 형성한다면 해당 간선은 건너뛰고 다음 간선부터 연결하는 알고리즘 기법입니다.
find()와 union() 은 사이클을 형성하는지 판단하기 위해 사용합니다.
그렇다면 이 문제는 왜 플래티넘일까?
간선의 가중치가 제대로 주어지지 않았기 때문입니다.
두 행성을 연결할 때 필요한 가중치는 다음과 같습니다.
두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)
그렇다면 N개의 행성이 주어졌을 때 각 행성 끼리의 간선을 구하고 해당 간선 중에서 가중치가 작은 것 부터 더해나가면 되지 않나요?
플래티넘 부터는 입력의 개수를 보셔야 합니다.
입력의 개수 (1 ≤ N ≤ 100,000)
행성 간 모든 간선의 개수를 구하면 그 개수는 N(N-1)… 즉, 통상적으로 1초의 연산의 마지노선이라는 1억번의 연산을 가뿐히 넘겨버립니다.
해결책은 다음과 같습니다.
Arrays.sort(points, (o1, o2) -> o1.x - o2.x);
for (int i = 0; i < N - 1; i++) {
pq.add(new Node(points[i].idx, points[i + 1].idx,
Math.abs(points[i].x - points[i + 1].x)));
}
Arrays.sort(points, (o1, o2) -> o1.y - o2.y);
for (int i = 0; i < N - 1; i++) {
pq.add(new Node(points[i].idx, points[i + 1].idx,
Math.abs(points[i].y - points[i + 1].y)));
}
Arrays.sort(points, (o1, o2) -> o1.z - o2.z);
for (int i = 0; i < N - 1; i++) {
pq.add(new Node(points[i].idx, points[i + 1].idx,
Math.abs(points[i].z - points[i + 1].z)));
}
C
복사
최종 코드
package baekjoon.graph.kruskal;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class _2887 {
static int[] parent;
static PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
Point[] points = new Point[N];
parent = new int[N];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
for (int i = 0; i < points.length; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
points[i] = new Point(i, x, y, z);
}
Arrays.sort(points, (o1, o2) -> o1.x - o2.x);
for (int i = 0; i < N - 1; i++) {
pq.add(new Node(points[i].idx, points[i + 1].idx,
Math.abs(points[i].x - points[i + 1].x)));
}
Arrays.sort(points, (o1, o2) -> o1.y - o2.y);
for (int i = 0; i < N - 1; i++) {
pq.add(new Node(points[i].idx, points[i + 1].idx,
Math.abs(points[i].y - points[i + 1].y)));
}
Arrays.sort(points, (o1, o2) -> o1.z - o2.z);
for (int i = 0; i < N - 1; i++) {
pq.add(new Node(points[i].idx, points[i + 1].idx,
Math.abs(points[i].z - points[i + 1].z)));
}
int answer = 0;
while (!pq.isEmpty()) {
Node temp = pq.poll();
if (find(temp.from) != find(temp.to)) {
union(temp.from, temp.to);
answer += temp.weight;
}
}
System.out.println(answer);
}
public static int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
public static void union(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
parent[y] = x;
}
}
static class Point {
int idx;
int x;
int y;
int z;
public Point(int idx, int x, int y, int z) {
this.idx = idx;
this.x = x;
this.y = y;
this.z = z;
}
}
static class Node {
int from;
int to;
int weight;
public Node(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
}
JavaScript
복사
