오늘은 서로소 집합을 활용한 Union-Find 알고리즘에 대해 학습해보도록 하겠습니다. 이는 이후 공부할 최소신장트리의 기반이 되기 때문에 꼭 이해해두시길 바랍니다.

서로소 집합(Disjoint-set)

▪️ 서로소 집합이란 서로 중복 포함된 원소가 없는 집합들을 의미합니다. 즉, 교집합이 없습니다.

▪️ 대표자란 각 집합들을 구분하는 집합에 속한 하나의 특정 멤버를 의미합니다.

▪️ 서로소의 집합 표현은 연결리스트, 트리를 통해 할 수 있습니다.

💡 트리로 서로소 집합 표현

▪️ 같은 집합의 원소들을 하나의 트리로 표현하게 됩니다.

▪️ 자식 노드가 부모 노드를 가리키고 있으며, 루트 노드를 대표자로 합니다.

⭐️ 필요한 연산 종류

서로소 집합은 다음 연산들만 이해한다면 구현하기 매우 간단합니다.

1. Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산입니다.
2. Find-Set(x) : x를 포함하는 집합을 찾는 연산 즉, 대표자를 찾는 연산입니다.
3. Union(x,y) : x와 y를 포함하는 두개의 집합을 합치는 연산입니다.
   ⚠️ 집합끼리 합친다는 것 유의! ⚠️

이러한 연산들을 코드로 작성해보면 다음과 같습니다.

코드 구현

public class DisjointsetTest {
	static int N; // 초기 집합의 개수
	static int parents[]; // 부모 배열

	public static void make() {
		parents = new int[N];
		// 모든 요소는 자기만 원소로 갖는 단위 서로소 집합 즉, 자신이 대표자인 루트로 표현.
		for (int i = 0; i < N; i++) {
			parents[i]=i;
		}
	}

	// 대표자 찾는 함수, union 내부에서도 활용 
	public static int find(int x) {
		// 기저조건 
		if(parents[x]==x) return x; // 자기 자신이 부모이면 x 리턴

		// 자신이 대표자가 아니면 내 부모를 따라서 대표자를 탐색 
		return find(parents[x]);
	}

	// x가 속한 집합과 y가 속한 집합을 합칠 수 있다면 합친 후, true 아니면 false 반환.
	public static boolean union(int x, int y) {
		int xRep = find(x);
		int yRep = find(y);

		if(xRep == yRep) return false; // 대표자가 같은 경우 union 필요 x 

		// 대표자가 다르므로 합치기 가능 
		// Union 처리 - yRep를 xRep 아래로 붙인다 가정
		parents[yRep] = xRep;
		return true;
	}

	public static void main(String[] args) {
		N=5;

		make(); // 단위 서로소 집합 만들기

		/** 테스트를 진행하고 싶으면 주석을 제거하세요.

		// 단위 서로소 집합 잘 만들어졌는지 Test
		for(int i=0;i<N;i++) {
			System.out.println("find("+i+") : "+find(i));
		}

		// union(0,1) 진행 
		System.out.println(union(0, 1));

		// union(0,1) 잘 됐는지 Test
		for(int i=0;i<N;i++) {
			System.out.println("find("+i+") : "+find(i));
		}

		// union(2,1) 진행 
		System.out.println(union(2, 1));

		// union(2,1) 잘 됐는지 Test
		for(int i=0;i<N;i++) {
			System.out.println("find("+i+") : "+find(i));
		}

		// union(3,2) 진행 
		System.out.println(union(3, 2));

		// union(3,2) 잘 됐는지 Test
		for(int i=0;i<N;i++) {
			System.out.println("find("+i+") : "+find(i));
		}

		// union(4,3) 진행 
		System.out.println(union(4, 3));

		// union(4,3) 잘 됐는지 Test
		for(int i=0;i<N;i++) {
			System.out.println("find("+i+") : "+find(i));
		}

		 */

	}
}

위에 코드는 다음과 같이 Path Compression 최적화를 진행해 볼 수 있습니다.

✔️ Path Compression이란 Find-Set(x) 연산에서 만나는 모든 노드들이 직접 root 즉, 대표자를 가리키도록 포인터를 바꿔주는 방법입니다.

이러한 Path Compression 최적화를 진행하면 find 함수 속 return 문이 다음과 같이만 변경시키면 됩니다.

	// 대표자 찾는 함수, union 내부에서도 활용 
	public static int find(int x) {
		// 기저조건 
		if(parents[x]==x) return x; // 자기 자신이 부모이면 x 리턴

		// 자신이 대표자가 아니면 내 부모를 따라서 대표자를 탐색 
		return find(parents[x]);
	}

	// 대표자 찾는 함수, union 내부에서도 활용 
	public static int find(int x) {
		// 기저조건 
		if(parents[x]==x) return x; // 자기 자신이 부모이면 x 리턴

		// 자신이 대표자가 아니면 내 부모를 따라서 대표자를 탐색 
		return parents[x]=find(parents[x]); // path Compression 활용한 최적화 진행 
	}

여기까지 자신이 이해했는지 문제를 통해 안보고 직접 Union-Find를 구현해 보면서 복습하시면 좋을 것 같습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr