[ 알고리즘 ] 코딩 백준 2887 - 행성 터널.java

백준 2887 - 행성터널

* 자바로 구현

* 행성의 위치는 x,y,z 의 좌표로 주어짐.
* 행성간 터널을 뚫는데, A(x1,y1,z1) - B(x2,y2,z2)가 주어지고
* min(|x1-x2|,|y1-y2|,|z1-z2|)를 구하면 된다.
* 예를들어 A(1,2,3) B(10, 2, 32) 인 경우에는 y좌표가 같으므로 비용은 0이 된다.
* 행성 10만개.. 좌표값 -10^9 ~ + 10^9

---

* X좌표를 기준으로 정렬하고 Edge 추가
* Y좌표를 기준으로 정렬하고 Edge 추가
* Z좌표를 기준으로 정렬하고 Edge 추가
​
* 모든 Edge를 가중치를 기준으로 오름차순 정렬
* 정렬 된 Edge에 대해서 Kruskal 적용

public class BOJ_2887_Planet_Tunnel {
	static int N; // 전체 행성의 수
	static List<Planet> plist = new ArrayList<>(); // 행성 저장 리스트
	static List<Edge> elist = new ArrayList<>(); // 간선 저장 리스트
	static int[] parents; // 크루스칼 알고리즘을 적용할 집합 배열
	
	static class Planet{ // 행성의 정보를 저장할 class
		int x, y, z; // x, y, z 좌표
		int vertex_number; // 행성 번호

		public Planet(int x, int y, int z,int vertex_number) { // 생성자
			this.vertex_number = vertex_number;
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}

	static class Edge implements Comparable<Edge>{ // 간선 정보를 저장할 class
		int from, to, weight; // 출발지점, 도착지점, 가중치

		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) { // comparable 인터페이스를 구현. 정렬에 사용 할 수 있게
			return this.weight - o.weight; // 가중치 기준으로 간선들 정렬
		}
	}

	public static void main(String[] args) throws Exception{
        // 10만개의 행성 정보를 입력받아야 하기 때문에 
        // 속도를 높이기 위해서 BufferedReader와 StringTokenizer를 이용
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stt = new StringTokenizer(br.readLine());

		N = Integer.parseInt(stt.nextToken());
		
		for( int vertex = 0; vertex < N; vertex++) { // 행성의 정보를 입력받아 리스트 저장
			stt = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(stt.nextToken());
			int y = Integer.parseInt(stt.nextToken());
			int z = Integer.parseInt(stt.nextToken());
			plist.add(new Planet(x,y,z,vertex));
		}

		// 가중치 정보 입력
		input_Edge_Info();
		// 입력 된 X,Y,Z좌표의 가중치 모두 정렬
		Collections.sort(elist);
		// 서로소 집합 만들기
		makeSet();
		int result = 0, cnt = 0;
		
		// 모든 간선에 대해서 kruskal 실행
		for ( Edge e : elist) {
			if(unionSet(e.from, e.to)) {
				result += e.weight;
				if(++cnt == N - 1) break;
			}
		}
		System.out.println(result);
	}

	/** 
     * 합집합 만들기
     * 두 집합이 다른 집합이면 하나의 집합으로 합쳐준다.
     */
	private static boolean unionSet(int from, int to) {
		int aroot = findSet(from);
		int broot = findSet(to);
		
		// 이미 같은 집합이라면 false
		if( aroot == broot) return false;
		
		parents[broot] = aroot;
		return true;
	}

	/** 자신이 속한 집합찾기 */
	private static int findSet(int num) {
		if(parents[num] == num) return num;
		return parents[num] = findSet(parents[num]);
	}
	
	/** 가중치 정보 입력*/
	// for문 2번 돌리면 상당한 부하. 메모리가 오버한다.
	// x,y,z 하나씩 for문 하나로 반복하는 것이 더 효율적
	/** 가중치 정보 입력*/
	private static void input_Edge_Info() {
		// 각각 x, y, z에 대해서 정렬하고 가중치를 저장하는 가능.
		// 람다식으로 한 번 표현해봤다.
		Collections.sort(plist, (o1,o2) -> o1.x - o2.x);
		for( int i = 0; i < N-1; i++) {
			int weight = Math.abs(plist.get(i).x - plist.get(i+1).x);
			elist.add(new Edge(plist.get(i).vertex_number, plist.get(i+1).vertex_number, weight));
		}
		
		Collections.sort(plist, (o1,o2) -> o1.y - o2.y);
		for( int i = 0; i < N-1; i++) {
			int weight = Math.abs(plist.get(i).y - plist.get(i+1).y);
			elist.add(new Edge(plist.get(i).vertex_number, plist.get(i+1).vertex_number, weight));
		}
		
		Collections.sort(plist, (o1,o2) -> o1.z - o2.z);
		for( int i = 0; i < N-1; i++) {
			int weight = Math.abs(plist.get(i).z - plist.get(i+1).z);
			elist.add(new Edge(plist.get(i).vertex_number, plist.get(i+1).vertex_number, weight));
		}
	}

	/** 서로소 만들기*/
	private static void makeSet() {
		parents = new int[N+1];
		for( int i = 1; i <= N; i++) {
			parents[i] = i;
		}
	}
}