백준 | 2887번. 행성 터널 - MST 문풀

⬛ 백준 2887번. 행성 터널 - MST 문풀

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

출력

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

---

🎈  모든 행성 간의 모든 간선 정보를 구하면 안되는 이유

단순하게 생각하면 모든 행성들 간 서로 (x, y, z) 좌표값이 있기 떄문에, 모든 행성과 다른 모든 행성간의 좌표 차이 절댓값이 최소인 간선을 pQ에 모두 담은 뒤 N-1개의 간선을 잇는다는 생각이 들었다.

 이중 for문 돌아도 시간초과가 안날 거라 생각해서 단순하게 풀었는데, ㅎㅎ 시간 초과 대신 메모리 초과가 떴다 ^^

하지만 이 방식은 행성이 최대 10만개씩 주어지면 약 100만 만큼의 비교 데이터가 발생해서 메모리 초과가 발생한다. 이중 for문을 돌며 모든 행성 간의 간선 정보를 구하는 방식은 메모리 초과가 난다는 말이다.

모든 간선 정보 담으면 메모리 초과

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] =i;
		
		List<Planet> list = new ArrayList<>();
		for(int i=0; i<N; i++) {
			int x= kb.nextInt();
			int y = kb.nextInt();
			int z =kb.nextInt();
			list.add(new Planet(x, y, z));
		}
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
        	// 이중 for문 돌면서 모든 행성 간의 가중치 간선 정보를 pQ에 담은 모습
		for(int i=0; i<N; i++) {
			Planet cur = list.get(i);
			
			for(int j=i+1; j<N; j++) {
				Planet p = list.get(j);
				
				int min = Math.min(Math.abs(cur.x-p.x), Math.min(Math.abs(cur.y-p.y), Math.abs(cur.z-p.z)));
				pQ.offer(new Edge(i+1, j+1, min));
			}
		}

---

💚 문제 접근 방식 - 필요한 간선만을 담자

이중 for문을 돌면서 모든 간선을 구하는 방법으로는 이 문제를 해결할 수 없다는 결론에 이른다.

그렇다면 필요한 간선만을 담자는 생각으로 전환이 되는데, 어떻게 필요한 간선만 추출해낼 수 있을까 ?

이 문제는 결국 모든 행성을 연결할 때 ‘최소 비용’으로 연결하고 싶은 거다.

x, y, z 각각에 대한 좌표 오름차순 정렬하여 가까운 정점끼리의 간선 정보만 추출해내면 된다

1. x 좌표 기준 행성 오름차순 정렬 시킨 뒤, 바로 옆 정점 간의 좌표 차만 pQ에 담는다.
2. y좌표 기준 행성 오름차순 정렬 시킨 뒤, 바로 옆 정점 간의 좌표 차만 pQ에 담는다.
3. z좌표 기준 행성 오름차순 정렬 시킨 뒤, 바로 옆 정점 간의 좌표 차만 pQ에 담는다.

→ 이제 이 상황에서 pQ는 자동 오름차순 정렬되어 있고, MST가 사이클을 허용하지 않으면서 union 처리를 하기 때문에 자연스럽게 최단 경로로 N-1개의 간선을 연결할 수 있게 된다.

필요 간선만 추출해야 맞는다.

💚 제출 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 2887번. 행성 터널 - MST 문풀 
 * @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 s, e, val;
	Edge(int s, int e, int val){
		this.s= s;
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int[] parent;
	//find
	static int find(int a) {
		if(a==parent[a]) return a;
		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);
		int N = kb.nextInt();
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i] =i;
		
		List<Planet> pList = new ArrayList<>();
		for(int i=0; i<N; i++) {
			int x= kb.nextInt();
			int y = kb.nextInt();
			int z =kb.nextInt();
			pList.add(new Planet(i+1, x, y, z))	;
		}
		
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		Collections.sort(pList, (p1, p2) -> Integer.compare(p1.x, p2.x));
		for(int i=1; i<N; i++) {
			int val = Math.abs(pList.get(i).x - pList.get(i-1).x);
			pQ.offer(new Edge(pList.get(i).num, pList.get(i-1).num, val));
		}
		
		Collections.sort(pList, (p1, p2) -> Integer.compare(p1.y, p2.y));
		for(int i=1; i<N; i++) {
			int val = Math.abs(pList.get(i).y - pList.get(i-1).y);
			pQ.offer(new Edge(pList.get(i).num, pList.get(i-1).num, val));
		}
		
		Collections.sort(pList, (p1, p2) -> Integer.compare(p1.z, p2.z));
		for(int i=1; i<N; i++) {
			int val = Math.abs(pList.get(i).z - pList.get(i-1).z);
			pQ.offer(new Edge(pList.get(i).num, pList.get(i-1).num, val));
		}
		
		int useEdge= 0;
		int useCost = 0;
		
		while(useEdge < N-1) {
			Edge edge = pQ.poll();
			if(find(edge.s) != find(edge.e)) {
				union(edge.s, edge.e);
				useCost += edge.val;
				useEdge++;
			}
		}
		System.out.println(useCost);
	}
}

이전에 푼 적 있는 문제를 다시 풀었는데,
다시 풀면서 또 메모리 초과가 떴다. 문제를 보면서 더 최적화 된 방법을 고려하고 풀이하자.

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