[백준 2887 - JAVA] 행성터널

2887번: 행성 터널

모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다!

간선을 찾고 MST로 연결하는 것은 쉽지만,

행성의 개수가 100,000개로 시간초과 혹은 메모리 초과가 발생하는 문제다.

나같은 경우에도 메모리 초과를 3번 겪고난 후 다른 블로그를 참고하여 문제를 해결했다.

 

 

풀이 방법

1. 각 행성의 Index와 x, y, z를 저장하고 Union-Find에서 사용할 배열을 초기화한다.
2. 행성들의 거리를 계산하여 간선으로 PQ에 삽입한다.

   2-1. 모든 간선을 삽입할 경우 시간초과, 메모리 초과가 발생한다.

   2-2. 간선을 최소화로 넣기 위하여 X, Y, Z 각각을 기준으로 정렬 후 가까운 행성끼리의 간선만을 삽입한다.

3. 크루스칼 알고리즘을 사용하여 최소 신장 부분 그래프를 완성한다.

 

 

 

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

public class Main {
	public static class Planet {
		int idx;
		int x, y, z;
		public Planet(int idx, int x, int y, int z) {
			this.idx = idx;
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
	
	public static int N;
	public static int ans;
	public static int[] p;
	public static Planet[] planets;
	public static PriorityQueue<int[]> pq;
	
	public static void union(int x, int y) {
		p[findSet(y)] = p[findSet(x)];
	}
	public static int findSet(int x) {
		if (p[x] == x) return x;
		return p[x] = findSet(p[x]);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[2], o2[2]);
			}
		});
		N = Integer.parseInt(br.readLine());
		planets = new Planet[N];
		p = new int[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			planets[i] = new Planet(i, x, y, z);
			p[i] = i;
		}
		
		createEdge();
		int cnt = 0;
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			if (findSet(cur[0]) != findSet(cur[1])){
				ans+=cur[2];
				if (++cnt == N-1) break;
				union(cur[0], cur[1]);
			}
		}
		
		System.out.println(ans);
	}
	
	public static void createEdge() {
		Arrays.sort(planets, new Comparator<Planet>() {
			@Override
			public int compare(Planet o1, Planet o2) {
				return Integer.compare(o1.x, o2.x);
			}
		});
		for (int i = 1; i < N; i++) {
			int dis = Math.abs(planets[i].x-planets[i-1].x);
			pq.add(new int[] {planets[i].idx, planets[i-1].idx, dis});
		}
		
		Arrays.sort(planets, new Comparator<Planet>() {
			@Override
			public int compare(Planet o1, Planet o2) {
				return Integer.compare(o1.y, o2.y);
			}
		});
		for (int i = 1; i < N; i++) {
			int dis = Math.abs(planets[i].y-planets[i-1].y);
			pq.add(new int[] {planets[i].idx, planets[i-1].idx, dis});
		}
		
		Arrays.sort(planets, new Comparator<Planet>() {
			@Override
			public int compare(Planet o1, Planet o2) {
				return Integer.compare(o1.z, o2.z);
			}
		});
		for (int i = 1; i < N; i++) {
			int dis = Math.abs(planets[i].z-planets[i-1].z);
			pq.add(new int[] {planets[i].idx, planets[i-1].idx, dis});
		}
	}
}