[BOJ] 백준 2887번 행성 터널 (Java)

#2887 행성 터널

난이도 : 골드 1

유형 : 그래프 탐색 / 최소 스패닝 트리(MST)

2887번: 행성 터널

▸ 문제

때는 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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

▸ 출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

문제 풀이  

모든 행성 터널을 최소 비용으로 연결하는 즉, 모든 정점을 최소 비용으로 연결하는 최소 스패닝 트리(MST) 문제이다.

1. 트리란 싸이클이 존재하지 않는 그래프이므로 유니온파인드를 사용하여 MST를 구할 수 도 있고, 
2. 기본적인 그래프 탐색 방식으로 모든 정점에 대한 간선을 구해서 BFS 탐색 방식으로 구할 수도 있다.

 

일단 해당 문제는 정점V의 최대 갯수가 10만개이다. 최대 간선의 갯수는 10만(10만-1)/2 = 대략 500억 정도 된다. 이정도 간선의 갯수는 메모리 초과를 불러오기 때문에 지금은 프림이나 크루스칼로 돌려도 풀지 못한다. 그래서 MST로 접근하기 전에 최적화 작업을 이뤄야 한다. 필요한 간선만 골라내는 것이다. 

 

간선 최적화 작업 이루기

주어진 정점에 대한 간선을 모두 구하면 대략 500억개이다. 그래서 필요한 간선만 추려낼 것이다. 현재 문제는 3차원으로 이루어져 있다. 단순하게 1차원으로 압축시켜보자.

 

(x, y, z) → x 또는 y 또는 z 평면으로만 이루어져 있는 공간이라면 최적의 간선을 골라내기 쉬워진다. 그냥 오름차순으로 정렬해서 인접해 있는 정점에 대한 간선만 구하면 된다.

• 이렇게 구하면 총 3*(N-1)의 간선을 구할 수 있게 된다. 그러면 최대 30만개 선에서 간선을 추려낼 수 있게 된다.
• 해당 방식이 적용되는 이유는 행성간의 거리 비용이 min(|xA-xB|, |yA-yB|, |zA-zB|)이기 때문이다. 만약, 3차원 정점 간의 거리를 구하는 공식이었다면 MST + 기하 문제가 되었을 것이고 정점의 수를 적게 줬을 것이다. 최적화 작업이 어려워지기 때문이다.

 

최소 스패닝 트리 적용하기

위에서 말한 1번이 크루스칼 알고리즘이고, 2번이 프림 알고리즘이다. 접근 방식을 보면 알겠지만 차이는 정점 위주로 탐색할 것이냐 아니면 간선 위주로 탐색할 것이냐 이다. 

• 간선의 개수가 적은 경우는 크루스칼 알고리즘
• 간선의 개수가 많은 경우는 정점 위주인 프림 알고리즘

 

나는 처음에 당연히 프림 알고리즘으로 해야 한다고 생각했다. 데이터가 정점은 10만개이고 간선은 30만개 안팎이기 때문이다. 그런데 두 알고리즘 결과를 비교해보니 크루스칼이 좀 더 빠르게 나왔다. (큰 차이는 아니지만 서도...) 

 

다시 생각해보니 중복되는 데이터가 존재해서 간선은 10만개라고 생각하는 것이 맞다. p1, p2 두 행성간의 비용이 각 x, y, z 평면의 경우에 따라 비용을 넣었기 때문에 간선과 정점의 수는 거의 일치한다고 봐야한다. 입력 할 때 해당 부분에 중복 데이터는 최소 비용으로 갈아치우는 방식으로 최적화를 이룰 수도 있겠다. 

• 그런데 사실상 난 30만개 중복된 데이터를 분별하지도 않았다.  그냥 TC 데이터가 크루스칼 쪽으로 더 최적화되게 주어졌다고 생각한다. 
• 크루스칼은 데이터를 바로 우선순위 큐에 넣어줘서 탐색을 돌리기 전에 이미 최소 비용 간선으로 정렬이 되어있다. 반면 프림은 정점 위주로 입력받아서 시작 정점(start)를 기준으로 최소 스패닝 트리를 탐색하기 때문에 발생한 차이다.
• 그런데 30만개나 10만개나 억단위도 아니고 비교하는 것 자체가 무의미하다고 생각이 든다. 크루스칼, 프림의 차이점에 대해서만 인지하고 넘어가자.

 

결론은 해당 문제는 크루스칼 알고리즘 , 프림 알고리즘 그냥 편한걸 사용하면 된다. 

 

크루스칼 풀이 코드

1. int[] 배열에 행성에 대한 초기 데이터를 입력받아 List에 저장한다.  data.add(new int[] {i, x, y, z});
2. 각 x, y, z 좌표 순으로 오름차순으로 정렬하여 인접한 정점끼리의 거리를 구한다.
3. 크루스칼 알고리즘을 사용할 것이므로  p1과 p2에 대한 간선 데이터를 큐에 저장한다.
   1. q.add(new Node(p1[0], p2[0], dis));
4. 크루스칼 알고리즘을 돌린다. (Union-Find + 우선순위 큐)
   
   1. 간선에 대한 비용이 적은 순으로 싸이클이 형성되기 전까지 탐색한다.
   2. 루트 노드가 일치하지 않으면 비용을 더해준다.
5. 구한 최소 비용을 출력한다.

import java.io.*;
import java.util.*;

public class Main {

	static class Node implements Comparable<Node>{
		int to;
		int from;
		int value;
		
		public Node(int to, int from, int value) {
			super();
			this.to = to;
			this.from = from;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}
	
	static int n;
	static int[] parents;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		List<int[]> data = new ArrayList<>();
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st =  new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			data.add(new int[] {i, x, y, z});
		}
		
		
		Queue<Node> q = new PriorityQueue<>();
		for(int idx=1; idx<=3; idx++) {
			int v = idx;
			Collections.sort(data, (o1,o2) -> (o1[v] - o2[v]));
			for(int i=1; i<n; i++) {
				int[] p1 = data.get(i-1);
				int[] p2 = data.get(i);
				int dis = Math.abs(p1[idx]-p2[idx]);
			
				q.add(new Node(p1[0], p2[0], dis));
			}
		}
		
		parents = new int[n];
		for(int i=0; i<n; i++) {
			parents[i] = i;
		}
		
		int total=0;
		while(!q.isEmpty()) {
			Node node = q.poll();
			int rx = find(node.to);
			int ry = find(node.from);
			
			if(rx != ry) {
				total += node.value;
				union(node.to, node.from);
			}
		}
		System.out.println(total);
	}
	
	static int find(int x) {
		if(parents[x] == x) {
			return x;
		}
		return parents[x] = find(parents[x]);
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x < y) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		parents[y] = x;
	}
}

 

프림 풀이 코드

1. int[] 배열에 행성에 대한 초기 데이터를 입력받아 List에 저장한다.  data.add(new int[] {i, x, y, z});
2. 각 x, y, z 좌표 순으로 오름차순으로 정렬하여 인접한 정점끼리의 거리를 구한다.
3. 프림 알고리즘을 사용할 것이므로 각 정점을 기준으로 간선의 양방향 정보를 입력한다.  
   1. list[p1[0]].add(new Node(p2[0],dis));
   2. list[p2[0]].add(new Node(p1[0],dis));
4. 프림 알고리즘을 돌린다. (BFS + 우선순위 큐)
   
   1. 간선에 대한 비용이 적은 순으로 방문하지 않은 노드를 방문한다.
   2. 방문한 노드에 대한 비용을 더해준다.
5. 구한 최소 비용을 출력한다.

import java.io.*;
import java.util.*;

public class Main {

	static class Node implements Comparable<Node>{
		int to;
		int value;
		
		public Node(int to, int value) {
			this.to = to;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
		
	}
	
	static int n;
	static List<Node>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		List<int[]> data = new ArrayList<>();
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st =  new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			data.add(new int[] {i, x,y,z});
		}
		
		list= new ArrayList[n+1];
		for(int i=0; i<n; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int idx=1; idx<=3; idx++) {
			int v = idx;
			Collections.sort(data, (o1,o2) -> (o1[v] - o2[v]));
			for(int i=1; i<n; i++) {
				int[] p1 = data.get(i-1);
				int[] p2 = data.get(i);
				int dis = Math.abs(p1[idx]-p2[idx]);
				
				list[p1[0]].add(new Node(p2[0],dis));
				list[p2[0]].add(new Node(p1[0],dis));
			}
		}
		prim(0);
		
	}
	
	static void prim(int start) {
		Queue<Node> pq = new PriorityQueue<>();
		boolean[] checked = new boolean[n];
		pq.add(new Node(start, 0));
		
		long total=0;
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			int node = cur.to;
			long value = cur.value;
			
			if(checked[node]) continue;
			
			checked[node] = true;
			total += value;
			
			for(Node nxt : list[node]) {
				if(!checked[nxt.to]) {
					pq.add(nxt);
				}
			}
		}
		System.out.println(total);
	}
}

 

 

실행 결과

 

크루스칼 알고리즘 실행결과

프림 알고리즘 실행결과