[백준] 행성 연결 16398 [JAVA]

출처 : www.acmicpc.net/problem/16398

16398번: 행성 연결

문제

홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다.

두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다.

모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다.

N개의 행성은 정수 1,…,N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다.

제국의 참모인 당신은 제국의 황제 윤석이를 도와 제국 내 모든 행성을 연결하고, 그 유지비용을 최소화하자.  이때 플로우의 설치비용은 무시하기로 한다.

입력

입력으로 첫 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.

두 번째 줄부터 N+1줄까지 각 행성간의 플로우 관리 비용이 N x N 행렬 (Cij),  (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji) 로 주어진다.

출력

모든 행성을 연결했을 때, 최소 플로우의 관리비용을 출력한다.

풀이방법 - 크루스칼

1. MST 구성하는 문제라고 바로 떠올랐다.

2. 입력 값을 봤을 때, 거의 행성 간 모든 간선이 주어지며, 배열 형태로 들어오는 것으로 보아 프림 알고리즘이 적당하다고 생각 했다.

3. 하지만, 아직 프림 알고리즘은 구현해보지 못해서 익숙한 크루스칼을 활용했다.(내일은 프림으로 다시 풀어봐야겠다.)

4. 시간이 오래걸림 ! : 행성의 관리비용 값이 최대 1억 까지 들어온다.
--> 모든 관리비용을 더하면 21억 ( int )을 초과하는 경우가 발생하므로 int 형으로하면 틀린 답이 된다. -> long형

** 범위는 항상 잘 체크해야 한다.

코드

package 알고리즘스터디문제;

import java.util.PriorityQueue;
import java.util.Scanner;

public class 행성연결_16398 {

	static int N;
	static int[][] map;
	static PriorityQueue<planet> pq = new PriorityQueue<>();
	static int[] parents, rank;
	static long answer = 0, count = 0;

	public static class planet implements Comparable<planet> {
		int from;
		int to;
		int weight;

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

		@Override
		public int compareTo(planet o) {
			// TODO Auto-generated method stub
			return this.weight - o.weight;
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt(); // 행성 수

		// input
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();

				// 본인 행성아니면
				if (map[i][j] != 0 && j>=i) {
					pq.add(new planet(i, j, map[i][j]));
				}
			}
		}

		// initialize
		parents = new int[N];
		rank = new int[N];
		for (int i = 0; i < N; i++) {
			parents[i] = i;
			rank[i] = 0;
		}
		
		//print();

		// 1. 크루스칼 알고리즘 가중치 가장 작은 것 부터 우선순위 큐 정렬
		kruskal();
		// union - find 연산 처리 과정을 통해서 모든 집합 형성되면 끝!
		System.out.println(answer);
	}

	private static void kruskal() {
		// TODO Auto-generated method stub

		while (!pq.isEmpty()) {

			// 1. 처음부터 하나씩 꺼내면서 from 과 to가 같은 집합이 아니라면 ,
			planet cur = pq.poll();
			int cur_from = cur.from;
			int cur_to = cur.to;
			int cur_weight = cur.weight;

			// 같은 집합이 아니라면?
			int px = parent(cur_from);
			int py = parent(cur_to);
			if (px != py) {
				
				// 2. pq.weight 더하고
				// 3. 같은 집합으로 업데이트하자.
				union(px, py);
				answer += cur_weight;
				//count ++;
			}
			//if ( count == N-1) break;
		}

	}

	private static void union(int px, int py) {
		// TODO Auto-generated method stub
		parents[px] = py;
//		if ( rank[px] > rank[py]) {
//			parents[px] = py;
//			
//		}
//		else {
//			
//		}
	}

	private static int parent(int node) {

		if (parents[node] == node) {
			return node;
		} else {

			parents[node] = parent( parents[node] );
			return parents[node];
		}

	}

	private static void print() {
		// TODO Auto-generated method stub
		int pqlength = pq.size();
		for (int i = 0; i < pqlength; i++) {
			planet p = pq.poll();
			System.out.println("pq_from : " + p.from + " pq_to : " + p.to + " pq_weight : " + p.weight);
		}
	}
}