[BOJ 2887] 행성터널

문제

• BOJ 2887
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

처음에 모든 간선이 이어져있다고 가정했는데 현재 문제에서 주어진 최대 정점의 수가 10만개이므로 최대 간선의 수는 10만(10만-1)/2 = 약500억이라 메모리초과가 나게 된다. 따라서 x,y,z좌표에 대해 각각 오름차순하면 i, i+1번 정점의 거리차가 작아지게 되는데 이 두 정점을 연결해준다. 이렇게 되면 총 3(N-1)번만에 간선을 정할 수 있다.

1) 각 정점의 번호,x,y,z좌표를 node[][]배열에 넣는다.
2) 간선을 연결하기 위한 makeAdjList()를 호출한다.

• x,y,z좌표를 기준으로 각각 오름차순한다.
• 오름차순 된 결과 현재 좌표를 기준으로 거리차가 가장 짧은 정점끼리 연결시킨다. 즉, 앞에서 부터 i, i+1번 정점을 연결시키는데 인접리스트 adjList에 양방향으로 넣는다.
• 만약 i, i+1번 정점에 대해 x1-x2, y1-y2가 두번이상 들어가더라도 나중에 pq에서 최소값만 꺼내주기 때문에 상관없다.

3) 간선정보가 다 만들어졌으면 prim()에서 프림알고리즘을 수행한다.

• 0번 정점을 시작점으로 해서 pq에 넣는다. pq에서 현재까지 뽑은 정점의 모든 간선정보를 관리한다.
• pq에서 아직 방문하지 않았고 가장 최소비용을 가진 정점을 뽑는다.
• b에서 뽑은 정점에 연결된 모든 간선정보를 pq에 넣는다.
• 모든 노드가 연결될 때 까지 b~c를 반복한다.

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

//프림 알고리즘
public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N, x, y, z, w;
	static int[][] node; // 정점 정보
	static ArrayList<Node>[] adjList; // 인접리스트
	static boolean[] visited;
	static long Ans;
	static StringTokenizer st;
	static PriorityQueue<Node> pq;

	static class Node implements Comparable<Node> {
		int num;
		int w;

		public Node(int num, int w) {
			this.num = num;
			this.w = w;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.w, o.w);
		}
	}

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

		node = new int[N][4];
		adjList = new ArrayList[N];

		for (int i = 0; i < N; i++) adjList[i] = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			node[i][0] = i; // idx
			node[i][1] = Integer.parseInt(st.nextToken()); // x
			node[i][2] = Integer.parseInt(st.nextToken()); // y
			node[i][3] = Integer.parseInt(st.nextToken()); // z
		}

		makeAdjList(); // 인접리스트 만들기
		prim(); //프림알고리즘
		System.out.println(Ans);
	}

	private static void prim() {
		visited = new boolean[N];
		pq = new PriorityQueue<>();
		pq.add(new Node(0, 0));

		int cnt = 0;
		while (!pq.isEmpty()) {
			Node now = pq.poll();
			if (visited[now.num]) continue;
			visited[now.num] = true;
			Ans += now.w;

			if (++cnt == N) break;
			
			for (Node next : adjList[now.num]) pq.add(next);
		}
	}

	private static void makeAdjList() {
		// 각 좌표(x,y,z)에 대해 오름차순 후 앞에서부터 거리비용의 차가 작은 두 정점씩 이어준다(메모리초과 방지)
		for (int idx = 1; idx <= 3; idx++) {
			int v = idx;
			Arrays.sort(node, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return Integer.compare(o1[v], o2[v]);
				}
			});

			for (int i = 0; i < N - 1; i++) {
				int[] n1 = node[i];
				int[] n2 = node[i + 1];
				int d = Math.abs(n1[v] - n2[v]);
				adjList[n1[0]].add(new Node(n2[0], d));
				adjList[n2[0]].add(new Node(n1[0], d));
			}
		}
	}
}