Union-Find C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <malloc.h>
#include <climits>
using namespace std;

const int MAX_SIZE = 101;

int parent[MAX_SIZE];
int rankArr[MAX_SIZE];

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

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

void Union(int a, int b) {
    int A = Find(a);
    int B = Find(b);

    if (A == B) return;
    if (rankArr[A] < rankArr[B]) {
        parent[A] = B;
    }
    else if (rankArr[A] > rankArr[B]) {
        parent[B] = A;
    }
    else {
        parent[B] = A;
        rankArr[A]++;
    }
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

   
    

    return 0;
}

유니온 파인드란?

유니온 파인드(Union-Find)는 **상호 배타적 집합(Disjoint Set)**을 관리하는 데 사용되는 자료구조입니다. 주로 다음과 같은 두 가지 연산을 효율적으로 수행합니다:

1. Find: 특정 원소가 속한 집합의 루트 노드를 찾습니다.
2. Union: 두 원소가 속한 집합을 하나로 합칩니다.

이 자료구조는 Kruskal 알고리즘, 그래프의 연결 성분 확인, 사이클 검출 등 다양한 분야에서 활용됩니다.

---

핵심 개념

1. 트리 구조로 집합 표현

각 집합을 트리로 표현하며, 루트 노드가 집합의 대표가 됩니다. 모든 노드는 부모 노드를 가리키며, 루트 노드의 부모는 자기 자신입니다.

2. 경로 압축(Path Compression)

Find 연산 시 트리의 높이를 줄여 이후 연산의 효율성을 높입니다.

3. Union by Rank

두 트리를 합칠 때 높이가 낮은 트리를 높은 트리 아래에 붙여 균형을 유지합니다.

---

코드 분석

초기화

int parent[MAX_SIZE];
int rankArr[MAX_SIZE];

void initialize() {
    for (int x = 0; x < MAX_SIZE; x++) {
        parent[x] = x;  // 자기 자신을 부모로 설정
        rankArr[x] = 0; // 초기 랭크는 0
    }
}

• parent[]: 각 노드의 부모 저장
• rankArr[]: 해당 노드를 루트로 하는 트리의 높이 저장

---

Find 연산

int Find(int x) {
    if (x == parent[x]) return x;         // 루트 노드
    return parent[x] = Find(parent[x]);   // 경로 압축
}

• 경로 압축: 찾는 경로 상의 모든 노드가 루트를 직접 가리키게 함 → 이후 연산 속도 향상

---

Union 연산

void Union(int a, int b) {
    int A = Find(a);
    int B = Find(b);

    if (A == B) return; // 이미 같은 집합

    // Union by Rank
    if (rankArr[A] < rankArr[B]) {
        parent[A] = B;
    } else {
        parent[B] = A;
        if (rankArr[A] == rankArr[B]) {
            rankArr[A]++;
        }
    }
}

• 높이가 작은 트리를 큰 트리 아래에 병합
• 두 트리의 높이가 같다면 한쪽의 랭크 증가

---

예제 코드

int main() {
    initialize();
    
    Union(1, 2);
    Union(2, 3);
    Union(4, 5);

    cout << "Find(3): " << Find(3) << endl; // 1
    cout << "Find(5): " << Find(5) << endl; // 4

    Union(3, 5);
    cout << "Find(5): " << Find(5) << endl; // 1
}

출력 결과

Find(3): 1
Find(5): 4
Find(5): 1

---

시간 복잡도

연산시간 복잡도

Find	O(α(N)) (거의 상수 시간)
Union	O(α(N))

• α(N): 애커만 함수의 역함수로 매우 느리게 증가

---

활용 사례

1. Kruskal 알고리즘: 최소 신장 트리 구현
2. 그래프 연결성 확인: 두 노드가 같은 연결 요소에 속하는지 확인
3. 사이클 검출: 무방향 그래프에서 사이클 존재 여부 판단

---

장단점

장점

• 구현이 간단하고 효율적
• 거의 상수 시간에 연산 가능

단점

• 방향 그래프의 사이클 검출에는 부적합

 

 

기초문제 

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

SW Expert Academy