[알고리즘] 서로소 집합

서로소 집합(Disjoint-set)

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합으로 교집합이 없다.
• 대표자 : 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.
• 서로소 집합을 표현하는 방법 : 연결리스트, 트리

서로소 집합 연산

• Make-Set(x) : 최소 단위 집합 생성
• Find-Set(x) : x가 속한 집합 찾기 or x가 속한 집합 대표자 찾기
• Union(x,y) : x가 속한 집합, y가 속한 집합이 서로소 집합일 때 합쳐서 하나의 집합으로 만들기 ==> 서로소 집합이 유지 되어야 함.

서로서 집합 표현 : 연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
• 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.

서로소 집합 표현 : 트리

• 같은 집합의 원소들을 하나의 트리로 표현한다.
• 자식 노드가 부모노드를 가리키며 루트 노드가 대표자가 된다.

서로소 집합 구현 코드(java)

import java.util.Arrays;

public class DisjointSetTest {
	
	static int N;
	static int[] parents;
	
	//  단위 집합 생성
	public static void makeSet() {
		parents = new int[N];
		// 자신의 부모노드를 자신의 값으로 세팅
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
	}
	// a의 집합 찾기 : a의 대표자 찾기
	public static int findSet(int a) {
		if(a==parents[a]) return a;
		return	parents[a] = findSet(parents[a]); // path compression
	}
	// a,b 두 집합 합치기
	public static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot) return false;

		parents[bRoot] = aRoot;
		return true;
	}

	public static void main(String[] args) {
		// 테스트
		N = 5;
		makeSet();

		System.out.println(Arrays.toString(parents));
		System.out.println(union(0,1));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(2,1));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(3,2));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(4,3));
		System.out.println(Arrays.toString(parents));

		System.out.println("===========find===========");
		System.out.println(findSet(4));
		System.out.println(Arrays.toString(parents));
		System.out.println(findSet(3));
		System.out.println(Arrays.toString(parents));
		System.out.println(findSet(2));
		System.out.println(Arrays.toString(parents));
		System.out.println(findSet(0));
		System.out.println(Arrays.toString(parents));
		System.out.println(findSet(1));
		System.out.println(Arrays.toString(parents));

	}
}