백준 | 2887번. 행성 터널 - 최소비용 신장트리 문풀

⬛ 백준 2887번. 행성 터널 - 최소비용 신장트리 문풀

https://www.acmicpc.net/problem/2887

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

출력

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

---

💚나의 풀이

• 이 문제는 보통의 최소 비용 신장 트리 문제와 풀이법이 유사하다.
• 문제의 핵심은 N이 100,000 인데, 이중 for문을 돌지 않고 (돌면 초과 뜸) 어떻게 두 행성간 연결 비용을 계산하고 최소 비용으로 모든 행성을 연결할 것이냐에 달려있다.
• 우선 N개의 행성 정보들을 입력받아서 x,y,z 각각의 좌표를 기준으로 정렬한 뒤 정렬된 상태에서의 인접한 행성 간 좌표값을 빼서 우선순위 큐에 넣으면 ‘우선순위 큐’에는 자동으로 가중치 낮은 간선이 순서대로 담겨있게 된다.
• 간선에 가중치만 잘 처리했다면, 보통의 최소비용 신장트리 문제와 동일하다. N개의 정점에 대하여 N-1개의 간선을 (사이클 X) 최소 비용으로 연결한다면 그 값의 가중치 합이 문제가 요구하는 답이 된다.

💚나의 코드

package to_1228_2;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 2887번. 행성 터널 - 최소비용신장트리 문풀 -> 정리하기 
 * @author MYLG
 *
 */
class Planet{
	int num;
	int x, y, z;
	Planet(int num, int x, int y, int z){
		this.num = num;
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

class Edge implements Comparable<Edge>{
	int st, ed, val;
	Edge(int st, int ed, int val){
		this.st = st;
		this.ed = ed;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;//가중치 적은 거 우선임
	}
}
public class Main {
	static int N;
	static int[] parent;
	//find
	static int find(int a) {
		if(a == parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] = i;//자기 자신으로 우선 초기화
		
		Planet[] pList = new Planet[N];
		for(int i=0; i<N; i++) {
			int x = kb.nextInt();
			int y = kb.nextInt();
			int z = kb.nextInt();
			pList[i] = new Planet(i, x, y, z);
		}
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		//x좌표 기준으로 정렬 
		Arrays.sort(pList, (p1, p2) -> Integer.compare(p1.x, p2.x));
		for(int i=1; i<N; i++) {
			int val = Math.abs(pList[i].x - pList[i-1].x);
			pQ.offer(new Edge(pList[i].num, pList[i-1].num, val));
		}
		
		//y좌표 기준으로 정렬 
		Arrays.sort(pList, (p1, p2) -> Integer.compare(p1.y, p2.y));
		for(int i=1; i<N; i++) {
			int val = Math.abs(pList[i].y - pList[i-1].y);
			pQ.offer(new Edge(pList[i].num, pList[i-1].num, val));
		}
		//z좌표 기준으로 정렬 
		Arrays.sort(pList, (p1, p2) -> Integer.compare(p1.z, p2.z));
		for(int i=1; i<N; i++) {
			int val = Math.abs(pList[i].z - pList[i-1].z);
			pQ.offer(new Edge(pList[i].num, pList[i-1].num, val));
		}
		
		int useEdge = 0, useCost=0;
		//mst
		while(useEdge != N-1) { //간선 N-1개 연결함
			Edge cur = pQ.poll();
			if(find(cur.st) != find(cur.ed)) {
				union(cur.st , cur.ed);
				useCost += cur.val;//가중치 합
				useEdge++;//간선 ++ 처리
			}
		}
		
		System.out.println(useCost);//최소비용	
	}
}