유니온파인드 이해하기 (예제코드 포함)

유니온 파인드(Union-Find)

유니온 파인드는 서로소 집합(Disjoint Set)을 표현하고 관리하기 위해 사용하는 자료구조입니다.

서로소 집합은 겹치는 원소가 없는 여러 그룹으로 나뉜 데이터를 표현하며, 대표적으로 그래프에서의 연결성 확인에 사용됩니다.

 

주요 연산

1. Find(찾기):
   • 특정 원소가 어떤 집합에 속해 있는지 확인합니다.
   • 집합을 식별할 수 있도록 각 집합에는 고유한 root가 있습니다.
   • x의 부모를 찾는 과정
   • 경로 압축(Path Compression)을 사용해 탐색 과정에서 트리의 깊이를 줄여 효율성을 높입니다.
2. Union(합치기):
   • 두 집합을 하나로 합치는 과정. 집합의 대표자를 기준으로 병합.
   • 일반적으로 한 집합의 루트를 다른 집합의 루트로 설정하여 합칩니다.

 

유니온 파인드 알고리즘의 특징

• 시간 복잡도:
  • 효율성을 위해 경로 압축(Path Compression)과 랭크 기반 합치기(Union by Rank)를 함께 사용할 경우,
  • 거의 O(1)에 가까운 시간 복잡도를 가집니다.
  • 이를 통해 최악의 경우에도 상수에 가까운 속도로 Find와 Union 연산을 수행합니다.
• 적용 사례:
  • 최소 신장 트리(Minimum Spanning Tree): Kruskal's Algorithm.
  • 그래프에서 연결 요소 찾기.

---

코드 설명 및 예제

 

1. 초기화

for(int i = 1; i <= n; i++) {
    parent[i] = i;
}

 

각 원소는 처음에 자기 자신을 부모로 설정합니다. 즉, 모든 원소가 독립적인 집합으로 초기화됩니다.

 

2. 찾기(Find)

private static int find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = find(parent[x]); // 경로 압축
}

• 재귀적으로 부모를 따라가며 최상위 루트를 찾습니다.
• 경로 압축을 통해 탐색한 모든 원소가 루트를 직접 가리키게 합니다.

 

 

3. 합집합(Union)

private static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a; // 한 집합으로 병합
}

 

• find를 통해 두 원소의 루트를 찾습니다.
• 두 루트가 다르면 하나의 집합으로 합칩니다.

 

 

4. 동일 집합 확인(Check Same)

private static boolean checkSame(int a, int b) {
    return find(a) == find(b);
}

 

두 원소의 루트를 비교하여 같은 집합에 속하는지 확인합니다.

 

예제 코드

https://true-false.tistory.com/39