백준 2887번 : 행성 터널 (Java)

 문제

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

2887번: 행성 터널

2887 행성 터널

 

 구현 방법

최소 스패닝 문제 이지만!!!!!

주어진 행성의 개수가 100,000개, 모든 행성 간의 거리를 구하면 100,000 * 99,999/2 = 약 500억개 이므로 사용하는 메모리가 메모리 제한인 128MB를 훨씬 초과하게 됩니다.

 

따라서 다른 방법을 찾아야 했지만 전 찾지 못했고^^ 질문 검색을 참고하여 풀었습니다.

 

행성을 터널로 연결할 때 드는 비용은 X 좌표 차이의 절대값, Y 좌표 차이의 절대값, Z 좌표 차이의 절대값 중 최소이니 3가지 좌표를 한 번에 계산 할 필요가 없습니다.

약간 플랫하게 X좌표만 생각해 봤을 때 주어진 행성들의 X 좌표를 비용 순으로 정렬하여 각 인접한 행성을 이어준다면 어떨까요?!?!?!?

예제를 예로 들어 X좌표를 비용 순으로 정렬한다면 -1(C) 10(D) 11(A) 14(B) 19(E) 입니다.

만약 C와 A 행성에 터널을 놓는다면 드는 비용은 12가 되겠죠.

하지만 C와 A 행성 사이에 D 행성이 존재하기 때문에  C-D, D-A에 터널을 놓는 것이 더 최소 비용으로 모든 행성을 연결할 수 있습니다.

따라서 좌표마다 비용 순으로 정렬하여 인접한 행성들로 간선을 만든 후 Kruskal 알고리즘을 사용하면 되겠죠?!

 

마찬가지로 Y좌표, Z좌표도 비용 순으로 정렬하여 리스트에 저장한다면 (100,000-1) * 3 = 약 30만개로 메모리를 훨씬 적게 사용하게 됩니다.

 

아래 그림은 예제를 위에 설명한 방식으로 푼 정리 입니다.

 

 구현 코드

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

public class Main {
	static int N, root[], cnt;
	static Value from, to;
	static List<Value> X = new ArrayList<>(), Y = new ArrayList<>(), Z = new ArrayList<>();
	static List<Edge> edgeList = new ArrayList<>();
	static class Edge implements Comparable<Edge>{ // 간선 저장할 클래스
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
        
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	static class Value implements Comparable<Value> { // 좌표 저장할 클래스
		int num, value;

		public Value(int num, int value) {
			super();
			this.num = num;
			this.value = value;
		}

		@Override
		public int compareTo(Value o) {
			return Integer.compare(this.value, o.value);
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		root = new int[N+1];
		StringTokenizer st = null;
		for (int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
            		// 각 좌표들 저장
			X.add(new Value(i, Integer.parseInt(st.nextToken())));
			Y.add(new Value(i, Integer.parseInt(st.nextToken())));
			Z.add(new Value(i, Integer.parseInt(st.nextToken())));
		}
		
        	// 좌표를 비용 순으로 정렬
		Collections.sort(X);
		Collections.sort(Y);
		Collections.sort(Z);
		
		for (int i=0;i<N-1;i++) {
        		// 각 좌표별로 인접한 터널 생성
			from = X.get(i); to = X.get(i+1);
			edgeList.add(new Edge(from.num, to.num, Math.abs(from.value-to.value)));
			from = Y.get(i); to = Y.get(i+1);
			edgeList.add(new Edge(from.num, to.num, Math.abs(from.value-to.value)));
			from = Z.get(i); to = Z.get(i+1);
			edgeList.add(new Edge(from.num, to.num, Math.abs(from.value-to.value)));
		}
		
		long ans = 0;
		makeSet();
		Collections.sort(edgeList); // 간선 리스트 비용 순으로 정렬
		for (Edge edge : edgeList) {
			if (union(edge.from, edge.to)) { // 만약 연결되지 않았다면 연결해주고
				ans += edge.weight; // 비용 더하기
				if (++cnt == N-1) { // 모든 행성을 연결하면 끝
					System.out.println(ans);
					System.exit(0);
				}
			}
		}
	}
	
	static void makeSet() {
		for (int i=0;i<N+1;i++) {
	        	// 초기에 아무것도 연결되지 않았으니 -1로 초기화	
			root[i] = -1; 
		}
	}
	
	static int findSet(int x) {
		if (root[x] < 0) return x; // 만약 0보다 작다 = 연결되지 않았다 root는 자기 자신
		return root[x] = findSet(root[x]); // 연결된 상단의 루트를 찾아서 리턴
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot) return false; // 루트가 같다 == 연결되었다
		root[bRoot] = aRoot; // 루트를 같게 한다 == 연결
		return true;
	}
}

 

정답!