[Theory] Graph 3. 서로소 집합(Disjoint-set) aka, Union-Find

서로소 집합(Disjoint-set), 혹은 상호배타 집합이라고도 하는 이놈은 서로 중복 포함된 원소가 없는 집합들을 말한다. 

즉, 교집합이 없다.

   또한, 이렇게 분리된 집합을 구분하기 위해, 집단에 속한 하나의 특정 구분자를 정하게 되는데 이를 대표자(representative) 라 한다. 이렇게 서로소 집합을 표현하는 방법에는 연결리스트를 이용하는 방법과, 트리를 이용하는 방법이 있다.

- 연결리스트 : 같은 집합의 원소들을 하나의 연결리스트로 관리해서, 대표자가 아닌 집합의 원소도 따라 들어가며 찾을 수 있다.

- 트리 : 형태가 트리라고 해서, 실제로 링크를 연결해서 구현한 것은 아니고, 대표자를 나타내는 배열 한줄로 각 집합들의 대표자를 관리하고, 대표자가 같은 두 원소는 같은 집합에 있다고 생각한다.

이 중 트리를 이용한 서로소 집합을 표현하는 Union-FInd 의 동작과정을 나타내면 다음과 같다.

[ 동작과정 ]

 

1. Make-Set( N ) : 먼저 집합의 요소들을 생성하고, 각각의 원소의 대표자는 자기자신이 되게 만든다.

static void make() { // 크기가 1인 단위집합을 만든다.
		for(int i=0; i<N; i++) {
			parents[i] = i;
		}
	}

 

 2. Find-Set( a ) : a를 포함하는 집합을 찾는 연산이다. 재귀방식으로 따라올라가면서 자신의 대표자를 찾는다.

이때 path compression 이라는 것이, 연산의 효율을 높이기 위해 사용된다.
    - path compression은 Find-Set을 하는 과정에서 만나는 모든 노드들이 대표자(Root)를 직접 가리키도록 포인터를 바꿔 줌으로서, 트리의 depth가 계속 깊어지는 것을 어느정도 막아준다. 위의 그림이 path-compression이 포함된 동작과정으로, 만약 적용이 되지 않았다면 find(d)를 하는 시점에 트리의 모양이 그대로였을 것이다.

	static int findSet(int a) {
		if(parents[a]==a) { // 내가 대표자인 경우
			return a;
		}
//		path compression 전
//		return findSet(parents[a]);
		
//		path compression 후
		return parents[a] = findSet(parents[a]); 
	}

 

3. Union( a, b ) : a와 b를 포함하는 두 집합을 하나의 집합으로 통합하는 연산이다.

이때 Union 연산을 하는 과정에서 연산이 잘 이루어 졌는지, 또 원래 같은 집합에 소속되어 있는 상황이였는지를 판단하기 위해 리턴값을 boolean으로 만들었다. 

	// union이 잘 처리되었는지 판단을 위한 리턴값
	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;
	}

 

워낙 유명하고, 이해하기도 쉬운 알고리즘 이지만 이런 개념을 처음 창조해낸 사람들이 참 대단하다고 느껴진다.

 

- 전체 코드

import java.util.Arrays;

public class DisjointSetTest {

	static int N;
	static int parents[];
	
	static void make() { // 크기가 1인 단위집합을 만든다.
		for(int i=0; i<N; i++) {
			parents[i] = i;
		}
	}
	
	static int findSet(int a) {
		if(parents[a]==a) { // 내가 대표자인 경우
			return a;
		}
//		path compression 전
//		return findSet(parents[a]);
		
//		path compression 후
		return parents[a] = findSet(parents[a]); 
	}
	
	// union이 잘 처리되었는지 판단을 위한 리턴값
	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;
		parents = new int[N];
		
//		1. make set
		make();
		
//		2. union
		System.out.println("=============union=============");
		System.out.println(union(0,1));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(1,2));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(3,4));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(0,2));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(0,4));
		System.out.println(Arrays.toString(parents));
		
//		3. find
		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));	
		
	}

}