[백준] 2887번 행성터널

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

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

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

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

[문제] 백준 2887번 : 행성터널

풀이 방법

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});
		}
	}
}

시간제한	메모리 제한	시간	메모리	레벨	풀이 당시 정답율
1초	128MB	1584ms	76588KB	골드 2	37.91%