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

https://www.acmicpc.net/problem/16398

16398번: 행성 연결

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

public class Main {
	static int[] parents;
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] matrix = new int[N][N];
		parents = new int[N];
		makeParents();
		List<Data> list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				if(matrix[i][j] != 0) list.add(new Data(i,j,matrix[i][j]));
			}
		}
		
		Collections.sort(list);
		int index =0;
		long answer =0;
		
		for(int i=0; i<list.size(); i++) {
			if(index == N-1)break;
			
			Data data = list.get(i);
			
			if(union(data.x, data.y)) {
				index++;
				answer += data.dis;
			}
		}
		
		System.out.println(answer);
	}
	
	public static void makeParents() {
		for(int i=0; i<N; i++) {
			parents[i] = i;
		}
	}
	
	public static int findParents(int a) {
		if(parents[a] == a) return a;
		
		return parents[a] = findParents(parents[a]);
	}
	
	public static boolean union(int a, int b) {
		int rootA = findParents(a);
		int rootB = findParents(b);
		
		if(rootA == rootB) return false;
		
		parents[rootB] = rootA;
		return true;
	}
}

class Data implements Comparable<Data>{
	int x;
	int y;
	int dis;
	public Data(int x, int y, int dis) {
		super();
		this.x = x;
		this.y = y;
		this.dis = dis;
	}
	@Override
	public int compareTo(Data o) {
		return this.dis - o.dis;
	}
}

정리

모든 행성 연결 and 최소 비용 찾기 -> 최소 스패닝 트리 문제였습니다.

N의 크기가 1000이고 정점끼리 다 연결이 되어 있다고 생각해도 간선이 500,000 안 쪽이기에 크루스칼 알고리즘을 이용해서 풀었습니다. 

처음 행렬을 입력받고 간선 데이터를 List로 저장하여 정렬하였고, 그 후의 계산은 전형적인 크루스칼 알고리즘을 안다면 쉽게 풀 수 있는 문제였습니다.

주의할 점은 플로우 관리 비용이 최대 100,000,000이기 때문에 결괏값을 long 형태로 안 해주면 틀립니다.

끝!