문제

백준 2887 행성 터널 문제 보러가기



해설

크루스칼 알고리즘을 사용해서 풀이했는데 처음엔 메모리초과가 발생했다. n이 최대 100,000이므로 이중 for문을 돌려서 정점과 정점사이 거리(dist)를 구하면 시간은 물론 메모리도 터진다.

이 문제의 핵심은 행성과 행성을 연결할 때 드는 비용이다.

비용 min = (|xA-xB|, |yA-yB|, |zA-zB|) 이므로 x, y, z 중 가장 작은 값을 비용으로 하기 때문에 행성과 행성사이의 최소 거리를 구하는것 보단 행성 사이의 좌표 x, y, z를 각각 오름차순으로 정렬해서 가장 가까운 행성끼리만 거리를 계산해준다. 즉, 1번 행성은 가장 가까운 2번 행성과의 거리만 구하고 2번 행성은 3번 행성과의 거리를 구한다. 굳이 1번 행성과 3번, 4번, … n번 행성 사이의 거리를 구하지 않아도 된다.

참고 블로그



풀이

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

public class Main {
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine()); // 행성의 개수

		Point[] pos = new Point[N];

		StringTokenizer st;

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

			pos[i] = new Point(i, x, y, z);
		}

		PriorityQueue<Edge> pq = new PriorityQueue<>();

		Arrays.sort(pos, (p1, p2) -> p1.x - p2.x); // x좌표 기준으로 정렬한다
		for (int i = 0; i < N - 1; i++) {
			int cost = Math.abs(pos[i].x - pos[i + 1].x);

			pq.add(new Edge(pos[i].num, pos[i + 1].num, cost));
		}

		Arrays.sort(pos, (p1, p2) -> p1.y - p2.y); // y좌표 기준으로 정렬한다
		for (int i = 0; i < N - 1; i++) {
			int cost = Math.abs(pos[i].y - pos[i + 1].y);

			pq.add(new Edge(pos[i].num, pos[i + 1].num, cost));
		}

		Arrays.sort(pos, (p1, p2) -> p1.z - p2.z); // z좌표 기준으로 정렬한다
		for (int i = 0; i < N - 1; i++) {
			int cost = Math.abs(pos[i].z - pos[i + 1].z);

			pq.add(new Edge(pos[i].num, pos[i + 1].num, cost));
		}

		parent = new int[N];

		for (int i = 0; i < N; i++) {
			parent[i] = i;
		}


		int answer = 0;
		while(!pq.isEmpty()) {
			Edge e = pq.poll();
			
			int findA = find(e.st);
			int findB = find(e.end);
			
			if (findA != findB) {
				parent[findB] = findA;
				answer += e.cost;
			}
		}

		System.out.println(answer);
	}

	static int find(int n) {
		if (parent[n] == n)
			return n;
		return parent[n] = find(parent[n]);
	}

	static class Edge implements Comparable<Edge> {
		int st, end, cost;

		public Edge(int st, int end, int cost) {
			this.st = st;
			this.end = end;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

	static class Point {
		int num, x, y, z;

		public Point(int num, int x, int y, int z) {
			this.num = num;
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
}