백준_행성 터널_2887

// 알고리즘

 

1.  최소 스패닝 트리

 

2. x,y,z좌표를 각각 listX,list,Y,listZ에 넣고 오름차순 정렬

 

3. 인접한 행성들끼리 연결시켜야 함.

 - 좌표를 담은 리스트들을 돌면서 인접한 행성을 list에 넣어줌

 - 크루스칼 알고리즘으로 MST 구함.

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

public class 행성터널_2887 {
	static int N, parent[];

	static class Point {
		int x, y, z, idx, from, to, cnt;

		public Point(int from, int to, int cnt) {
			super();
			this.from = from;
			this.to = to;
			this.cnt = cnt;
		}

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

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		parent = new int[N];

		List<Point> list = new ArrayList<>();
		List<Point> listX = new ArrayList<>();
		List<Point> listY = new ArrayList<>();
		List<Point> listZ = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());

			listX.add(new Point(x, y, z, i));
			listY.add(new Point(x, y, z, i));
			listZ.add(new Point(x, y, z, i));
		}

		listX.sort((o1, o2) -> o1.x - o2.x);
		listY.sort((o1, o2) -> o1.y - o2.y);
		listZ.sort((o1, o2) -> o1.z - o2.z);

		for (int i = 1; i < N; i++) {
			list.add(new Point(listX.get(i - 1).idx, listX.get(i).idx, Math.abs(listX.get(i - 1).x - listX.get(i).x)));
			list.add(new Point(listY.get(i - 1).idx, listY.get(i).idx, Math.abs(listY.get(i - 1).y - listY.get(i).y)));
			list.add(new Point(listZ.get(i - 1).idx, listZ.get(i).idx, Math.abs(listZ.get(i - 1).z - listZ.get(i).z)));
		}

		init();
		int ans = 0;
		int cnt = 0;
		list.sort((o1, o2) -> o1.cnt - o2.cnt);
		for (Point p : list) {
			if (cnt == N - 1)
				break;
			if (Union(p.from, p.to)) {
				cnt++;
				ans += p.cnt;
			}
		}

		System.out.println(ans);

	}

	private static boolean Union(int xx, int yy) {
		int x = find(xx);
		int y = find(yy);

		if (x == y)
			return false;
		parent[y] = x;
		return true;
	}

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

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

	}

}

 

※ 우선순위큐로 풀려고 했으나 구현이 오래걸릴거같아 힌트를 참고하여 풀었음... 시간날 때 다시한번 풀어봐야겠다.