그래프 이론 - 4. 행성터널

문제

때는 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좌표가 주어진다.
• 좌표는 -10^9보다 크거나 같고, 10^9보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

출력조건

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

입력 예시
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

출력 예시
4

구현코드

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

class Edge implements Comparable<Edge>{
	private int node1;
	private int node2;
	private int distance;
	public Edge(int node1, int node2, int distance){
		this.node1 = node1;
		this.node2 = node2;
		this.distance =  distance;
	}
	public int getNode1(){
		return this.node1;
	}
	public int getNode2(){
		return this.node2;
	}
	public int getDistance(){
		return this.distance;
	}
	@Override
	public int compareTo(Edge other){
		return Integer.compare(this.distance, other.distance);
	}
}

class Position implements Comparable<Position>{
	private int xyz;
	private int node;
	public Position(int xyz, int node){
		this.xyz = xyz;
		this.node = node;
	}
	public int getXyz(){
		return this.xyz;
	}
	public int getNode(){
		return this.node;
	}
	@Override
	public int compareTo(Position other){
		return Integer.compare(this.xyz, other.xyz);
	}
}
public class Main{
	public static int[] parent;
	public static ArrayList<Edge>edges = new ArrayList<>();
	
	public static int findParent(int a){
		if(a == parent[a]) return a;
		else return parent[a] = findParent(parent[a]);
	}
	public static void unionParent(int a, int b){
		a = findParent(a);
		b = findParent(b);
		if(a < b) parent[b] = a;
		else parent[a] = b;
	}
	
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		parent = new int[n+1];
		for(int i = 1 ; i <= n ; i ++){
			parent[i] = i;
		}
		ArrayList<Position>x = new ArrayList<>();
		ArrayList<Position>y = new ArrayList<>();
		ArrayList<Position>z = new ArrayList<>();
		for(int i = 1; i <= n; i++){
			st = new StringTokenizer(br.readLine());
			x.add(new Position(Integer.parseInt(st.nextToken()), i));
			y.add(new Position(Integer.parseInt(st.nextToken()), i));
			z.add(new Position(Integer.parseInt(st.nextToken()), i));
		}
		Collections.sort(x);
		Collections.sort(y);
		Collections.sort(z);
		
		// 인접한 노드들로부터 간선 정보를 추출하여 처리
		for(int i = 0 ; i < n-1 ; i++){
			edges.add(new Edge(x.get(i).getNode(), x.get(i+1).getNode(), x.get(i+1).getXyz() - x.get(i).getXyz()));
			edges.add(new Edge(y.get(i).getNode(), y.get(i+1).getNode(), y.get(i+1).getXyz() - y.get(i).getXyz()));
			edges.add(new Edge(z.get(i).getNode(), z.get(i+1).getNode(), z.get(i+1).getXyz() - z.get(i).getXyz()));
		}
		
		// 간선을 비용순으로 정렬
		Collections.sort(edges);
		
		int sum = 0;
		for(int i = 0 ; i < edges.size(); i++){
			Edge now = edges.get(i);
			int node1 = now.getNode1();
			int node2 = now.getNode2();
			int distance = now.getDistance();
			if(findParent(node1) != findParent(node2)){
				sum += distance;
				unionParent(node1, node2);
			}
		}
		
		System.out.println(sum);
	}
}

코드해석

이 문제는 모든 x, y, z 좌표를 검사하면 메모리 초과 문제가 발생한다. 그렇다면 어떻게 줄일 것인가?
방법은 하나이다. x, y ,z 좌표를 각각 오름차순으로 정렬 한 후 i ,i+1 번 째 좌표를 비교하여 그 값들을 가지고 크루스칼 알고리즘을 진행해야 하는 것이다.
이게 가능 한 이유는 문제에서 x 좌표의 차이, y 좌표의 차이 , z 좌표의 차이 중 더 적은 값이 두 행성 사이의 거리가 되기 때문이다.