유니온 파인드(Union-Find) 알고리즘

유니온 파인드(Union-Find) 알고리즘은 여러 원소들을 몇 개의 그룹(집합)으로 나누고, 다음 두 연산을 빠르게 수행하는 데 목적이 있는 서로소 집합(Disjoint Set Union, DSU)을 효율적으로 관리하기 위한 자료구조이자 알고리즘입니다.

핵심 연산

1. Find(찾기)
   어떤 원소가 속한 집합(대표자, 루트 노드)을 찾는 연산.
   • 보통 트리 구조로 구현되고, 루트 노드가 그 집합의 대표자가 됩니다.
   • 경로 압축(Path Compression) 기법을 쓰면 시간 복잡도를 크게 줄일 수 있습니다.
2. Union(합치기)
   두 원소가 속한 집합을 하나로 합치는 연산.
   • 두 집합의 대표자를 찾아서 하나로 연결해 줍니다.
   • 보통 "랭크(rank) 기반 합치기" 또는 "사이즈 기반 합치기"를 사용해서 트리가 한쪽으로 치우치지 않게 만듭니다.

---

동작 원리 예시

예를 들어 {1}, {2}, {3}, {4} 네 개의 집합이 있다고 하면

1. 처음엔 각각 자기 자신이 루트 → {1}, {2}, {3}, {4}
2. Union(1, 2) → {1,2}, {3}, {4}
3. Union(3, 4) → {1,2}, {3,4}
4. Union(2, 3) → {1,2,3,4}

이제 Find(4)를 하면 4가 속한 집합의 루트(예: 1)를 반환합니다.

---

시간 복잡도

• 단순히 구현하면 O(log N) ~ O(N)까지 걸릴 수 있지만,
• 경로 압축 + 랭크 기반 합치기를 적용하면,
  거의 상수 시간(O(α(N)))에 동작합니다.
  (α(N)은 아커만 함수의 역함수인데, 실제 사용되는 범위에선 5 이하라 사실상 상수라고 봐요.)

---

주요 활용 예시

• 그래프의 사이클 판별
• 최소 신장 트리(MST, Kruskal 알고리즘)
• 네트워크 연결성 판별
• 클러스터링 문제 해결

---

간단한 C++ 코드 예시

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent, rankArr;

// 초기화: 자기 자신을 부모로 설정
void init(int n) {
    parent.resize(n+1);
    rankArr.resize(n+1, 0);
    for (int i = 1; i <= n; i++) parent[i] = i;
}

// Find: 루트 찾기 + 경로 압축
int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

// Union: 두 집합 합치기 (랭크 기반)
void unionSet(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (rankArr[a] < rankArr[b]) swap(a, b);
    parent[b] = a;
    if (rankArr[a] == rankArr[b]) rankArr[a]++;
}

int main() {
    init(5);
    unionSet(1, 2);
    unionSet(3, 4);
    unionSet(2, 3);
    cout << (find(4) == find(1)); // 1(같은 집합)
}

 

유니온 파인드를 사용한 문제 풀이:https://javacpp.tistory.com/166