[Platinum V] 행성 터널 - 2887
성능 요약
메모리: 92808 KB, 시간: 1828 ms
분류
그래프 이론(graphs), 최소 스패닝 트리(mst), 정렬(sorting)
문제 설명
때는 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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
최소 신장 트리를 구현할 때 가능한 모든 edge를 추가하면 시간 초과가 난다.
방법을 모르겠어서 찾아보니 터널 연결의 비용은 x값의 차이, y값의 차이, z값의 차이 중 작은 값이기 때문에 각각 x, y, z값을 기준으로 정렬한 후 인접한 두 노드를 연결할 x,y,z를 하나씩 추가하면 된다.
A, B, C가 있고
x값만 고려했을 때 A-B가 1, B-C가 2, A-C가 3이라면 B를 거치지 않고 A와 C를 연결할 이유가 없다. 최소 길이로 모든 노드들을 연결하려면 가까운 노드들부터 확인해야 하기 때문이다.
그렇게 가능한 edge를 모두 구현하고 프림 또는 크루스칼 알고리즘을 사용하면 된다.
1. 프림 알고리즘
package BOJ.Platinum.p5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class BOJ_2887_행성터널 {
static class Vertex {
int id;
int x;
int y;
int z;
public Vertex(int id, int x, int y, int z) {
this.id = id;
this.x = x;
this.y = y;
this.z = z;
}
}
static class Edge implements Comparable<Edge> {
int st;
int ed;
long dist;
public Edge(int st, int ed, long dist) {
this.st = st;
this.ed = ed;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.dist, o.dist);
}
}
static int N;
static Vertex[] pos;
// 시간 초과
// x기준 인접한 노드, y기준 인접한 노드, z기준 인접한 노드끼리만 연결해줘도 됨
// 세 거리 중 최소값이 두 노드를 연결한 edge니까 이렇게 해서 정렬하면 최소 노드만 갈 수 있게 됨
static List<Edge>[] adjList;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
pos = new Vertex[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
pos[i] = new Vertex(i, x, y, z);
}
adjList = new ArrayList[N];
for (int i = 0; i < N; i++)
adjList[i] = new ArrayList<>();
// x기준 정렬 후 간선 연결
Arrays.sort(pos, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
// TODO Auto-generated method stub
return o1.x - o2.x;
}
});
for (int i = 0; i < N - 1; i++) {
Vertex v1 = pos[i];
Vertex v2 = pos[i + 1];
long dist = Math.abs(v1.x - v2.x);
adjList[v1.id].add(new Edge(v1.id, v2.id, dist));
adjList[v2.id].add(new Edge(v2.id, v1.id, dist));
}
// y 정렬
Arrays.sort(pos, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
// TODO Auto-generated method stub
return o1.y - o2.y;
}
});
for (int i = 0; i < N - 1; i++) {
Vertex v1 = pos[i];
Vertex v2 = pos[i + 1];
long dist = Math.abs(v1.y - v2.y);
adjList[v1.id].add(new Edge(v1.id, v2.id, dist));
adjList[v2.id].add(new Edge(v2.id, v1.id, dist));
}
// z기준 정렬 후 간선 연결
Arrays.sort(pos, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
// TODO Auto-generated method stub
return o1.z - o2.z;
}
});
for (int i = 0; i < N - 1; i++) {
Vertex v1 = pos[i];
Vertex v2 = pos[i + 1];
long dist = Math.abs(v1.z - v2.z);
adjList[v1.id].add(new Edge(v1.id, v2.id, dist));
adjList[v2.id].add(new Edge(v2.id, v1.id, dist));
}
// prim
boolean[] visited = new boolean[N];
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.addAll(adjList[0]);
visited[0] = true;
int pick = 0;
long ans = 0;
while (pick < N - 1) {
Edge e = pq.poll();
if (visited[e.ed])
continue;
visited[e.ed] = true;
pick++;
ans += e.dist;
pq.addAll(adjList[e.ed]);
}
System.out.println(ans);
}
}
2. 크루스칼 알고리즘
인접 리스트가 아니라 모든 edge들의 list를 만들고, edge 사이의 거리가 작은 순서대로 정렬한 후 union을 진행한다.
package BOJ.Platinum.p5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ_2887_행성터널_kruskal {
static class Vertex {
int id;
int x;
int y;
int z;
public Vertex(int id, int x, int y, int z) {
this.id = id;
this.x = x;
this.y = y;
this.z = z;
}
}
static class Edge implements Comparable<Edge> {
int st;
int ed;
long dist;
public Edge(int st, int ed, long dist) {
this.st = st;
this.ed = ed;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return Long.compare(this.dist, o.dist);
}
}
static int N;
static Vertex[] pos;
// 시간 초과
// x기준 인접한 노드, y기준 인접한 노드, z기준 인접한 노드끼리만 연결해줘도 됨
// 세 거리 중 최소값이 두 노드를 연결한 edge니까 이렇게 해서 정렬하면 최소 노드만 갈 수 있게 됨
static List<Edge> edges;
static int[] p;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
pos = new Vertex[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
pos[i] = new Vertex(i, x, y, z);
}
edges = new ArrayList<>();
// x기준 정렬 후 간선 연결
Arrays.sort(pos, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
// TODO Auto-generated method stub
return o1.x - o2.x;
}
});
for (int i = 0; i < N - 1; i++) {
Vertex v1 = pos[i];
Vertex v2 = pos[i + 1];
long dist = Math.abs(v1.x - v2.x);
edges.add(new Edge(v1.id, v2.id, dist));
edges.add(new Edge(v2.id, v1.id, dist));
}
// y 정렬
Arrays.sort(pos, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
// TODO Auto-generated method stub
return o1.y - o2.y;
}
});
for (int i = 0; i < N - 1; i++) {
Vertex v1 = pos[i];
Vertex v2 = pos[i + 1];
long dist = Math.abs(v1.y - v2.y);
edges.add(new Edge(v1.id, v2.id, dist));
edges.add(new Edge(v2.id, v1.id, dist));
}
// z기준 정렬 후 간선 연결
Arrays.sort(pos, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
// TODO Auto-generated method stub
return o1.z - o2.z;
}
});
for (int i = 0; i < N - 1; i++) {
Vertex v1 = pos[i];
Vertex v2 = pos[i + 1];
long dist = Math.abs(v1.z - v2.z);
edges.add(new Edge(v1.id, v2.id, dist));
edges.add(new Edge(v2.id, v1.id, dist));
}
// kruskal
p = new int[N];
for (int i = 0; i < N; i++)
p[i] = i;
Collections.sort(edges);
long ans = 0;
int pick = 0;
for (int i = 0; i < edges.size(); i++) {
Edge e = edges.get(i);
int st = findSet(e.st);
int ed = findSet(e.ed);
if (st != ed) {
// union
p[ed] = st;
ans += e.dist;
pick++;
}
if (pick == N - 1)
break;
}
System.out.println(ans);
}
static int findSet(int x) {
if (p[x] != x)
p[x] = findSet(p[x]);
return p[x];
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 2225 - 합분해 (자바 Java) : DP (0) | 2022.10.02 |
---|---|
[백준] 1504 - 특정한 최단경로 (자바 Java) (0) | 2022.09.30 |
[백준] 9370 - 미확인 도착지 (자바 Java) (1) | 2022.09.30 |
[백준] 13549 - 숨바꼭질 3 (자바 Java) (0) | 2022.09.30 |
[백준] 4195 - 친구 네트워크 (자바 Java) (0) | 2022.09.29 |