[BOJ] 2887 행성 터널 JAVA

 

[문제]
https://www.acmicpc.net/problem/2887

2887번: 행성 터널

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.



[입력]
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.



[출력]
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

---

[Solution 1]
- 최소신장트리 문제
- 크루스칼 알고리즘 사용
- 간선 최소값을 구하는 과정(line 57~70)에서 메모리 or 시간초과

package boj2887_행성터널;

/* 최소신장트리 문제
 * 크루스칼 알고리즘
 * -> 메모리초과
 * weight의 min값 구하는 부분에서 100,000*99999/2*12(byte) > 128MB
 * */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Edge implements Comparable<Edge>{
		int start, end, weight;
		
		public Edge(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return weight-o.weight;
		}
	}
	
	static int n;
	static int[][] space;
	static PriorityQueue<Edge> pq = new PriorityQueue<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		space = new int[n][3];
		int [] parent = new int[n];
		
		int answer = 0;
		int weight = 0;
		
		//i행성의 좌표값 input
		for(int i=0; i<n; ++i) {
			st = new StringTokenizer(br.readLine());
			
			space[i][0] = Integer.parseInt(st.nextToken());		//x
			space[i][1] = Integer.parseInt(st.nextToken());		//y
			space[i][2] = Integer.parseInt(st.nextToken());		//z
		}
		
		//A행성-B행성 연결시 비용 : min(|xA-xB|, |yA-yB|, |zA-zB|)
		//i-j = j-i 이므로 j는 i부터 시작(두번 할 필요x)
		for(int i=0; i<n; ++i) {
			for(int j=i; j<n; ++j) {
				if(i == j) continue;
				
				//x
				weight = Math.abs(space[i][0]-space[j][0]);
				//x, y
				weight = Math.min(weight, Math.abs(space[i][1]-space[j][1]));
				//x, y, z
				weight = Math.min(weight, Math.abs(space[i][2]-space[j][2]));

				pq.add(new Edge(i, j, weight));
			}
		}
		
		//parent를 자신으로 초기화
		for(int i=0; i<n; ++i) {
			parent[i] = i;
		}
		
		//가중치 작은것(앞쪽idx)부터 선택하면서 크루스칼 알고리즘 실행
		int len = pq.size();
		for(int i=0; i<len; ++i) {
			Edge node = pq.poll();
			
			//사이클이 발생하지 않는 경우(시작노드와 도착노드의 루트노드가 같지않으면)
			//에 집합에 포함(union 함수 실행), 노드(터널) 연결
			if(ckCycle(parent, node.start) != ckCycle(parent, node.end)) {
				union(parent, node.start, node.end);
				answer += node.weight;
			}
		}
		
		System.out.println(answer);
	}
	
	//x가 속한 집합 찾기(사이클 발생 확인), 루트노드 반환
	static int ckCycle(int[] parent, int node) {
		//parent[node]가 현재 노드랑 다르면 루트노드가 따로 있으므로
		//루트노드 찾아서 올라가는 재귀
		if(parent[node] != node) {
			parent[node] = ckCycle(parent, parent[node]);
		}
		return parent[node];
	}
	
	//start, end 속한 집합 합치기
	static void union(int[] parent, int start, int end) {
		//start와 end노드의 루트노드 찾아서 저장
		start = ckCycle(parent, start);
		end = ckCycle(parent, end);
		
		//더 위에 있는(숫자가 작은) 노드가 루트노드가 됨
		if(start < end) parent[end] = start;
		else parent[start] = end;
	}
}

 

[Solution 2]
- 크루스칼 알고리즘 그대로 사용
- min값을 구하지 않고 우선순위 큐를 이용
- x, y, z 간선의 가중치를 각자 구한 후
- 가중치가 작은 순으로 정렬 후 노드를 연결하면 시간, 메모리 절약!

package boj2887_행성터널;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main2 {
	static class Edge implements Comparable<Edge>{
		int start, end, weight;
		
		public Edge(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}
		
		//가중치 오름차순 정렬
		@Override
		public int compareTo(Edge o) {
			return weight-o.weight;
		}
	}
	
	static class Node implements Comparable<Node> {
		int pos, num;		//좌표, 노드번호
		
		public Node(int pos, int num) {
			this.pos = pos;
			this.num = num;
		}
		
		//좌표 오름차순, 좌표가 같으면 노드순
		@Override
		public int compareTo(Node o) {
			if(pos == o.pos) return num - o.num;
			return pos - o.pos;
		}
	}
	
	static int n;
	static PriorityQueue<Edge> pq = new PriorityQueue<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int [] parent = new int[n];
		
		//우선순위 큐를 사용해서 정렬 해주지 않아도됨
		PriorityQueue<Node> x = new PriorityQueue<>();
		PriorityQueue<Node> y = new PriorityQueue<>();
		PriorityQueue<Node> z = new PriorityQueue<>();
		
		int answer = 0;
		
		//i행성의 좌표값 input
		for(int i=0; i<n; ++i) {
			st = new StringTokenizer(br.readLine());
			
			x.add(new Node(Integer.parseInt(st.nextToken()), i));
			y.add(new Node(Integer.parseInt(st.nextToken()), i));
			z.add(new Node(Integer.parseInt(st.nextToken()), i));
		}	
		
		//A행성-B행성 연결비용 : x,y,z좌표 계산값의 절대값 중 최솟값이지만 최솟값을 구하는 과정은 필요없음.
		//오름차순 후 비용이 작은 간선(터널)부터 연결해서 최소값을 계산하는 과정 없어도 ㄱㅊ
		//|xA-xB|
		for(int i=0; i<n-1; ++i) {
			Node A = x.poll();
			Node B = x.peek();
			pq.add(new Edge(A.num, B.num, Math.abs(A.pos - B.pos)));
		}
		
		//|yA-yB|
		for(int i=0; i<n-1; ++i) {
			Node A = y.poll();
			Node B = y.peek();
			pq.add(new Edge(A.num, B.num, Math.abs(A.pos - B.pos)));
		}
		
		//|zA-zB|
		for(int i=0; i<n-1; ++i) {
			Node A = z.poll();
			Node B = z.peek();
			pq.add(new Edge(A.num, B.num, Math.abs(A.pos - B.pos)));
		}
		
		//parent를 자신으로 초기화
		for(int i=0; i<n; ++i) {
			parent[i] = i;
		}
		
		//가중치 작은것(앞쪽idx)부터 선택하면서 크루스칼 알고리즘 실행
		int len = pq.size();
		for(int i=0; i<len; ++i) {
			Edge node = pq.poll();
			
			//사이클이 발생하지 않는 경우(시작노드와 도착노드의 루트노드가 같지않으면)
			//에 집합에 포함(union 함수 실행), 노드(터널) 연결
			if(ckCycle(parent, node.start) != ckCycle(parent, node.end)) {
				union(parent, node.start, node.end);
				answer += node.weight;
			}
		}
		
		System.out.println(answer);
	}
	
	//x가 속한 집합 찾기(사이클 발생 확인), 루트노드 반환
	static int ckCycle(int[] parent, int node) {
		//parent[node]가 현재 노드랑 다르면 루트노드가 따로 있으므로
		//루트노드 찾아서 올라가는 재귀
		if(parent[node] != node) {
			parent[node] = ckCycle(parent, parent[node]);
		}
		return parent[node];
	}
	
	//start, end 속한 집합 합치기
	static void union(int[] parent, int start, int end) {
		//start와 end노드의 루트노드 찾아서 저장
		start = ckCycle(parent, start);
		end = ckCycle(parent, end);
		
		//더 위에 있는(숫자가 작은) 노드가 루트노드가 됨
		if(start < end) parent[end] = start;
		else parent[start] = end;
	}
}