[BOJ] 2887 행성터널

BOJ 2887 행성터널 풀러가기

문제요약

• 우주 공간에 행성을 연결하는 터널을 만드려고한다.
• 행성은 3차원 좌표 위에 한 점이고, 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
• 모든 행성이 연결되게 하는 최소 비용을 출력한다.

접근방법

• 처음 시도한 방법

  • 각 행성을 그래프의 정점으로 생각하고 가능한 모든 간선의 수 N*(N-1)/2개 중 최소 비용순으로 신장트리를 구성하는 크루스칼 알고리즘을 이용해 모든 행성을 연결하는 최소 비용을 구한다.
  • 행성 개수의 범위가 최대 100,000이기 때문에 구성가능한 간선의 경우는 50억개이다. int형으로 출발 행성, 도착 행성, 간선의 길이 정보를 포함하는 Edge 클래스를 만들 경우 60GB의 저장공간이 필요하기 때문에 메모리 초과가 발생한다.

• 해결 방법
  

  • 행성 1과 행성2를 연결하는 방법은 x축으로 연결하기, y축으로 연결하기, z축으로 연결하기 세 가지가 있다.
  • 각 행성을 연결하는 최소 비용은 x, y, z 축을 기준으로 가장 짧은 하나만 선택하는 것이기 때문에 x, y, z축을 기준으로 거리순 정렬한다.
  • 그 후 x, y, z축을 기준으로 정렬한 행성 정보들을 가장 짧은 간선부터 연결하기 위해 모든 간선 정보를 저장하는 자료구조에 저장한 후 거리 순으로 한 번 더 정렬한다.
  • 행성 간의 거리가 가장 짧은 행성 정보부터 순차적으로 처리한다. 크루스칼 알고리즘을 이용해 행성 간의 연결 처리가 되지 않은 경우에는 union한다. union 과정이 행성의 수 - 1만큼 반복되면 되면 모든 행성이 연결된 것이므로 거리 비용을 출력한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static class Edge implements Comparable<Edge>{
		int from, to, weight;
		Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge e) {
			return this.weight - e.weight;
		}
	}
	static int N;
	static Edge[] edgeList;
	static int[] parents;
	static int[][] locX, locY, locZ;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = stoi(br.readLine());
		StringTokenizer st;
		edgeList = new Edge[(N-1)*3]; // 노드 개수에 따른 간선의 수 * (x, y, z 축)
		locX = new int [N][2];
		locY = new int [N][2];
		locZ = new int [N][2];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			locX[i] = new int[] {i,stoi(st.nextToken())}; // 노드 번호, 좌표입력
			locY[i] = new int[] {i,stoi(st.nextToken())};
			locZ[i] = new int[] {i,stoi(st.nextToken())};
		}
		// 각 기준 축 별로 오름차순 정렬
		Arrays.sort(locX,(a, b) -> a[1] - b[1]); 
		Arrays.sort(locY,(a, b) -> a[1] - b[1]);
		Arrays.sort(locZ,(a, b) -> a[1] - b[1]);
		int index = 0;
		for (int i = 0; i < N-1; i++) {
			edgeList[index++] = new Edge(locX[i][0], locX[i+1][0], Math.abs(locX[i][1] - locX[i+1][1]));
			edgeList[index++] = new Edge(locY[i][0], locY[i+1][0], Math.abs(locY[i][1] - locY[i+1][1]));
			edgeList[index++] = new Edge(locZ[i][0], locZ[i+1][0], Math.abs(locZ[i][1] - locZ[i+1][1]));
		}
		Arrays.sort(edgeList); // 길이가 짧은 순으로 정렬
		makeSet();
		
		int res = 0, count = 0;
		for (int i = 0; i < edgeList.length; i++) {
			if (union(edgeList[i].from, edgeList[i].to)) { // 
				res += edgeList[i].weight;
				if (++count == N-1) break;
			}
		}
		System.out.println(res);
	}

	private static void makeSet() {
		parents = new int[N];
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
	}
	private static int findSet(int a) {
		if (parents[a] == a)
			return a;
		return parents[a] = findSet(parents[a]);
	}
	private static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return false;
		parents[bRoot] = parents[aRoot];
		return true;
	}
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}