크루스칼 알고리즘

가장 적은 비용으로 모든 노드를 연결하기

• 이 코드는 집합을 구분 할 때도 사용할 수 있을 것이다.

1. make

• 생성하기
• 모든 원소를 자신의 대표자로 만든다.

// N은 노드의 개수이다.
void make() {
	parents = new int[N];
    for ( int i = 0 ; i<N ; i++ ) {
    	parents[i];
}

2. find

• A가 속한 집합의 대표자 찾기
• 대표자 값을 반환한다.

int find(int a){
	if ( a == parents[a] ) return a;
	return parents[a] = find(parents[a]);
}

3. union

• 두 원소를 하나의 집합으로 합차기
• boolean을 반환한다.
• ture 면 두개가 같은 집합이 아니라는 뜻이다.

boolean union(int a, int b){
	int a_root = find(a);
    int b_root = find(b);
    if ( a_root == b_root ) return false; 
    parents[b_root] = a_root;
    return true;
}

4. 크루스칼 알고리즘 예제

섬 연결하기
https://programmers.co.kr/learn/courses/30/lessons/42861?language=java

• 풀이 코드

public class Solution {
	static class Node implements Comparable<Node> {
		int a;
		int b;
		int cost;
		public Node(int a, int b, int cost) {
			this.a = a;
			this.b = b;
			this.cost = cost;
		}
		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
		
	}
	static int N;
	// 우선순위 큐로 구현해도 된다.
	static PriorityQueue<Node> road;
	static int[] parents;
	// 소속 찾기
	static int find(int param ) {
		if ( param == parents[param]) return param;
		return parents[param] = find(parents[param]);
	}
	static boolean union(int A, int B) {
		int A_union = find(A);
		int B_union = find(B);
		if ( A_union == B_union ) {
			return false;
			// 같은 집합이다.
		}
		parents[B_union] = A_union;
		return true;
	}
	
	
	static public int solution(int n, int[][] costs) {
		// 초기화
		int answer = 0;
		N = n;
		parents = new int[n];
		// 모든 원소를 자신의 대표자로
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
		Arrays.sort(costs, (e1,e2) -> e1[2] - e2[2]);
		int temp = 0;
		for(int[] arr : costs) {
        
			int a = arr[0];
			int b = arr[1];
			int cost = arr[2];
			
			if ( union(arr[0], arr[1] )) {
				answer += arr[2];
				temp += 1;
				if ( temp >= N ) break;
			}
			if ( temp >= n ) break;
		}
        return answer;
    }
}