Union-Find

Union-Find

서로소 집합 (Disjoint-Set)을 표현할 때 사용하는 그래프 알고리즘
집합을 트리 구조로 표현하여 임의의 두 노드(원소)가 서로 같은 그래프(집합)에 속하는지 판별

 

Disjoint-Set

공통 원소가 없는 "상호 배타적인" 부분집합들로 나눠진 원소들에 대한 정보를 표현하는 자료구조

 

 

Unoin 연산과 Find 연산으로 이루어짐

• Union : 두 원소가 속한 집합을 하나로 합침
• Find : 해당 원소가 속한 집합(루트 원소)을 반환

 

Union-Find 사용 예시

• 특정 두 개체가 같은 그룹에 속하는지 효율적으로 판별하기 위해 사용됨

1. 네트워크 연결 여부 판별
   • 여러 개의 컴퓨터가 서로 연결될 떄, 특정 두 컴퓨터가 같은 네트워크에 속해 있는지 확인
2. 최소 신장 트리 (MST) - 크루스칼 알고리즘
   • 최소 비용으로 모든 노드를 연결하는 그래프를 만들 때 사이클이 생기지 않도록 검사
3. 동일 집합 판별
   • 여러 개의 요소가 있을 때, 특정 두 요소가 같은 그룹에 속하는지 판별

 

Union-Find 특징

• 각 집합을 하나의 트리로 나타내는 것이 핵심 → 트리의 특성에 따라 빠른 시간으로 탐색과 합치기가 가능
• 시간복잡도는 평균적으로 O(log N)이지만 편향될 경우 O(N)이 될 수 있음
• 이를 최적화하는 방법으로 경로 압축 (Path Compression), Rank 기반 연산이 있고 시간복잡도를 상수에 가깝게 만들 수 있음

 

Union-Find 기본 구현

 

1. initialize

: parent[x]를 자기 자신으로 초기화

int parent[MAX_SIZE];

void initialize() {
	for(int x=0; x < MAX_SIZE; x++){
		parent[x] = x;
    	}
}

 

2. Find

: Node x의 Root를 찾기

→ 재귀함수로 부모 노드가 자기 자신일 때까지 타고 올라감 (루트에 도달할 때까지)

int find(int x){
	if (x == parent[x]) {
		return x;
    	}
    	else return find(parent[x]);
}

 

3. Union

: Node a와 Node b를 합치기

→ b의 root를 부모 a의 root로 연결

void union(int a, int b){
	int A = find(a);
    	int B = find(b);
    
    	if(A != B) {
    		parent[B] = A;
    	}
}

 

 

최적화 방법 - Path Compression

• find 연산 최적화
• find에서 root를 찾을 때 최악의 상황에서는 O(N)만큼의 계산이 요구됨
• find는 depth가 낮을 수록, 즉 트리의 높이가 낮을 수록 유리 !
• 매번 find 할 때 depth가 2 이상이면 Path Compression 수행

• 특징) Root node를 원하는 값으로 강제할 수 있음

int find(int x){
	if(x == parent[x]) return x;
    	return parent[x] = find(parent[x]);
}

 

 

최적화 방법 - Rank

• union 연산 최적화
• rank에 트리의 높이(rank)를 저장하고, 항상 높이(rank)가 더 낮은 트리를 높은 트리 밑에 넣기

• 특징) union 과정을 역추적할 수 있음 (롤백 가능)

void union(int a, int b){
	int A = find(a);
    	int B = find(b);
    
    	if(A == B) {
    		return;
    	}
    	if(rank[A] < rank[B]) {
			parent[A] = B;
    	}
    	else if(rank[A] > rank[B]) {
			parent[B] = A;
    	}
    	else {
    		parent[B] = A;
        	rank[A]++;
    	}
}