유니온-파인드(Union-Find) 알고리즘은 서로소 집합(Disjoint Set)을 관리하기 위한 데이터 구조로, 여러 개의 원소가 각각 독립적인 집합에 속해 있을 때, 두 원소가 동일한 집합에 속하는지 판별하거나 두 집합을 합치는 연산을 효율적으로 수행할 수 있는 알고리즘이다. 이 알고리즘은 그래프의 연결 성분을 찾거나 최소 신장 트리를 구성하는 등의 문제에서 자주 사용된다.
주요 연산
- Find(찾기): 특정 원소가 속한 집합을 찾는다. 이를 통해 두 원소가 같은 집합에 속해 있는지 확인할 수 있다.
- Union(합치기): 서로 다른 두 집합을 하나의 집합으로 합친다.
최적화 기법
- 경로 압축(Path Compression): Find 연산 시, 경로상의 모든 노드를 루트로 직접 연결하여 트리의 높이를 줄이는 방법이다. 이를 통해 이후의 Find 연산이 더 빠르게 이루어질 수 있다.
Find 연산에서 자신의 부모 노드만을 반환하게 만들 수도 있다. 최악의 경우인 그래프가 편향된 상태로 주어진 경우에 O(N)시간이 걸린다. 따라서 경로상의 모든 노드를 루트로 직접 연결하여 트리의 높이를 줄이면 상수 시간 내에 연산이 가능해지므로 경로 압축 기법을 사용하는 것이 좋다.
코드
#include <iostream>
using namespace std;
int parent[100001];
int Find(int x) {
if (x == parent[x]) return x;
return parent[x] = Find(parent[x]);//경로 압축
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (x > y) parent[y] = x;
else parent[x] = y;
}
bool isUnion(int x, int y) {
x = Find(x);
y = Find(y);
return x == y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int a, b;
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) parent[i] = i;
for (int i = 0; i < m; i++){
cin >> a >> b;
Union(a, b);
}
return 0;
}- 랭크에 의한 합치기(Union by Rank): Union 연산 시, 두 트리의 깊이를 비교하여 깊이가 작은 트리를 더 깊은 트리 밑에 붙이는 방법이다.
단순하게 집합을 합칠 경우, 트리의 깊이를 증가할 수 있다. 이 경우 트리가 더 깊어져서 연산을 복잡하게 만든다. 따라서 트리의 깊이를 비교해서 얕은 트리를 깊은 트리 밑에 붙임으로써 트리의 높이가 증가하는 것을 방지한다.
Weighted Union-Find
두 집합을 합칠 때, 각 집합의 크기를 비교하여 크기가 작은 집합을 큰 집합의 하위 트리에 붙인다. 이를 통해 트리의 높이가 증가하는 것을 방지한다.
Union by Rank 기법 중에서 가장 효율적으로 메모리를 관리할 수 있는 방법이 있다. parent배열 하나만을 사용하는 Weighted Union-Find 기법이다. parent배열을 음수 값으로 초기화 하여 트리의 크기와 부모 노드, 두 가지 정보를 동시에 저장하는 방식이다.
- 음수 값: 현재 노드가 루트 노드임을 나타내며, 이 음수 값의 절대값이 해당 집합의 크기를 나타낸다.
- 양수 값: 부모 노드의 인덱스를 나타낸다.
작동 방식
- 초기화: 모든 원소가 자기 자신을 가리키도록 설정한다. 이때, parent 배열의 값은 -1로 초기화되며, 이는 각 원소가 자기 자신이 루트이며 크기가 1임을 나타낸다.
- Find: 트리의 루트를 찾고, 경로 압축을 통해 트리의 높이를 줄인다.
- Union: 두 집합의 루트를 찾고, 크기를 비교하여 더 작은 집합을 더 큰 집합에 합친다. 이 때 parent 배열의 값을 갱신하여 트리의 크기도 업데이트한다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int parent[1000];
int Find(int x) {
if (parent[x] < 0) return x;//음수 값을 가진다면 x가 루트 노드
return parent[x] = Find(parent[x]);//경로 압축
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;//이미 같은 집합이므로 무시
if (parent[x] < parent[y]) {
parent[x] += parent[y];//x의 크기 증가
parent[y] = x;//y가 x를 루트로 가리키도록 한다
}
else {
parent[y] += parent[x];//y의 크기 증가
parent[x] = y;//x가 y를 루트로 가리키도록 한다
}
}
bool isUnion(int x, int y) {
x = Find(x);
y = Find(y);
return x == y;
}
int size(int x) {
return -parent[Find(x)];// 루트 노드의 절대값이 집합의 크기
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int a, b;
int n;
cin >> n;
fill(parent, parent + n, -1);
for (int i = 0; i < n; i++) {
cin >> a >> b;
Union(a, b);
}
cout << isUnion(1, 2) << ' ' << isUnion(4,1);
return 0;
}- sz배열을 사용한 Union by Rank
#include <iostream>
using namespace std;
int parent[100001];
int sz[100001];
int Find(int x) {
if (x == parent[x]) return x;
return parent[x] = Find(parent[x]);//경로 압축
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
sz[y] = 0;
parent[y] = x;
}
bool isUnion(int x, int y) {
x = Find(x);
y = Find(y);
return x == y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int a, b;
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) {
parent[i] = i;
sz[i] = 1;
}
for (int i = 0; i < m; i++) {
cin >> a >> b;
Union(a, b);
}
return 0;
}
개발 일기