[그래프 #5] 유니온 파인드(Union Find) 알고리즘을 활용한 문제 풀이 방법

Union Find

여러 개의 원소를 서로 묶는 작업을 효율적으로 처리하기 위한 알고리즘

일반적으로 disjoint-set(서로소 집합) 자료구조를 구현하는 데 사용

 

과정

집합 내에서 어떤 두 원소가 같은 집합에 속해 있는지 여부를 판단

Union : 서로 다른 두 집합을 결합하는 작업

Find : 특정 원소가 속한 집합의 대표 원소를 찾아보는 작업

 

---

 

Union 작업 - O(N)

void Union(int A, int B) {
	// A와 B의 부모를 확인
	int root_A = Find(A);
	int root_B = FInd(B);

	// 둘이 다른 그룹이면, B의 그룹을 A의 산하로 넣을 것
	if (root_A != root_B){
		parent[root_B] = root_A;
	}
}

A, B의 부모를 확인할 때, 현재 parent의 상황으로 비교하면 안 된다.

parent[A] == parent[B] 방식으로 비교할 시,

매번 그룹이 합쳐질 때마다(Union), 합쳐졌다는 업데이트(Find)를 꾸준히 안해줬다면 오류가 난다. 매번 합쳐질 때마다, 업데이트를 꾸준히 해야 한다면 시간복잡도가 그만큼 늘어나므로, 손해

 

---

 

Find 작업 - O(N)

int Find(int now) {
	// 종료 조건 : now의 parent가 now와 같으면(내가 대표값) -> 소속을 찾았다
	if (now == parent[now])
		return now;

	// 재귀 구성 : now의 parent가 now와 다르면(내가 대표 값이 아님) -> 나의 부모(parent)를 찾아가라
	//            -> Find(parent[now]);

  // + 나의 부모(소속)을 찾으면, 기록해놓아야 함
	// parent[now] = Find(parent[now]);

	// **경로 압축** : 경로 상의 모든 노드가 직접 루트 노드를 가리킴
	return parent[now] = Find(parent[now]);
}

경로 압축 후의 시간복잡도 : O(α(N)); ← α(n)은 매우 느리게 증가하는 함수(거의 상수)를 의미

 

---

 

Union - Find 알고리즘 (Basic)

/*
6 5
0 1
3 0
3 4
4 3
2 5
*/

#include <iostream>

using namespace std;

int N, M;
int parent[100];

int Find(int now) {
	if (now == parent[now])
		return now;

	return parent[now] = Find(parent[now]);
}

void Union(int A, int B) {

	int root_A = Find(A);
	int root_B = Find(B);

	if (root_A != root_B) {
		parent[root_B] = root_A;
	}

	return;
}

int main() {
	cin >> N >> M;

  // 각 원소는 자기 자신을 대표하는 집합으로 초기화
	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	int a, b;
	// 간선의 정보를 받아서 각 노드를 이어줌
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		Union(a, b);
	}

	int cnt = 0;

	// 집합의 개수 = 대표원소의 개수 이므로,
	// 본인이 대표원소라면, cnt에 추가
	for (int i = 0; i < N; i++) {
		if (Find(i) == i) cnt++;
	}

	cout << cnt; // 2
}

일반적으로 시간복잡도 O(N)을 가짐

 

---

 

Union-Find 알고리즘 응용

1. 소속 관리
   • 사원이 입사하면, 해당 사원을 자신이 속할 부서의 집합에 추가
   • 두 부서를 합병하거나, 부서를 나누는 등의 변경이 필요할 때
2. 데이터 관리
   • 네트워크에서는 노드들을 연결하는 엣지를 각각의 집합으로 관리
   • → 연결된 노드들 사이의 최단 경로 등을 계산 가능
3. 그래프 내에서의 순환 정보
   • 사이클이 존재하는 그래프인 지 판단 → 최소 스패닝 트리와 연관
4. 역순 유형
   • Find 연산이 먼저 수행되고, 그 결과를 이용하여 Union 연산을 수행하는 방식
   • 특정 시점 이전의 데이터베이스 상태를 복원하는 작업을 수행할 때 사용
   • 간선 제거 문제 → 분해는 조립의 역순이란 것을 생각하며 풀 것
5. 이미지 분할(Image Segmentation)
   • 이미지에서 서로 연결된 픽셀들을 같은 집합으로, 이미지 내의 객체를 분리하는 작업

 

---

 

시간복잡도를 고려한 Union-Find 알고리즘

 

Union by Rank 방식

집합의 높이(랭크)를 사용하여 두 집합을 합침

int rank[N] = {0, }; // rank는 0으로 초기화 -> 초기화 복잡도 낮춤

void Union(int a, int b) {
	int root_A = Find(a);
	int root_B = Find(b);

	if (root_A == root_B) return;    // root 노드가 같다면 업데이트 필요 x
	
	if (rank[root_A] < rank[root_B])  // root_A : 큰 rank , root_B : 작은 rank
		swap(root_A, root_B);          // rank가 같다면 상관 없음

	parent[root_B] = root_A;         // rank가 작은 대표 노드가 랭크가 큰 곳에 붙음
	rank[root_A]++;                  // A 집단의 크기 증가 -> 랭크 증가

장점

• Union 함수의 시간 복잡도를 O(log N)으로 유지할 수 있음
• 큰 크기의 집합이 많이 존재하는 경우에 효율적

---

Union by Size 방식

집합의 크기를 사용하여 두 집합을 합침

int Size[N] = {0, }; // Size는 0으로 초기화

void Union(int a, int b) {
	int root_A = Find(a);
	int root_B = Find(b);

	if (root_A == root_B) return;    // root 노드가 같다면 업데이트 필요 x
	
	if (Size[root_A] < Size[root_B])  // root_A : 큰 집단 , root_B : 작은 집단
		swap(root_A, root_B);          // 크기가 같다면 상관 없음

  parent[root_B] = root_A;
	Size[root_A] += Size[root_B];    // B가 A 집단에 들어갔으므로, A집단의 크기가 커짐

장점

• 집합의 크기를 찾거나, 두 집합의 크기를 비교할 때 용이
• 작은 크기의 집합이 많이 존재하는 경우에 효율적