[Algorithm] 서로소 집합(Disjoint Set)과 유니온 파인드(Union-Find) 정리

1. 서로소 집합(Disjoint Set)이란?

서로소 집합(Disjoint Set)은 겹치는 원소가 없는 집합들의 모임을 의미한다.

서로소 집합의 핵심 연산

서로소 집합을 다룰 때 핵심적으로 사용하는 연산은 다음과 같다.

1. makeSet(x): 각각의 원소를 독립적인 집합으로 초기화
2. findSet(x): 특정 원소 x가 속한 집합의 대표(루트) 찾기
3. union(x, y): 두 개의 집합을 합치기

서로소 집합의 활용

서로소 집합은 유니온-파인드(Union-Find) 알고리즘을 사용하여 효율적으로 집합 연산을 수행할 수 있다.
대표적인 활용 예시는 다음과 같다.

• 네트워크 연결 확인 (컴퓨터 네트워크, 친구 관계)
• 최소 신장 트리(MST, Kruskal's Algorithm)
• 동일 집합 여부 확인 (서로소 판별)
• 경로 압축(Path Compression) 기법을 통한 빠른 탐색

 

2. 유니온 파인드(Union-Find)란?

유니온 파인드(Union-Find) 알고리즘은 서로소 집합을 표현하고 연산을 효율적으로 수행하기 위한 알고리즘이다.

핵심 연산

1. findSet(x) → 원소 x가 속한 집합의 대표(루트) 찾기 (O(α(N)))
   • 경로 압축(Path Compression) 을 사용하여 탐색 시간을 줄일 수 있음.
2. union(x, y) → 두 개의 집합을 합침 (O(α(N)))
   • 랭크 기반 합치기(Rank Heuristic) 를 사용하여 최적화할 수 있음.
3. makeSet(x) → 초기 상태에서 자기 자신을 부모로 설정 (O(1))

📌 O(α(N))는 거의 상수 시간에 가깝기 때문에, 매우 빠르게 동작하는 알고리즘이다!
(α(N): 아커만 역함수, 실제 문제에서 거의 O(1))

 

예시 코드

import java.util.Arrays;

public class DisjointSet {
    
    private static int N;  // 정점의 개수
    private static int[] parents;  // 인덱스 번호: 정점 번호, 값: 부모 정점 번호
    
    // 단위 집합 생성 (초기화)
    private static void makeSet() {
        parents = new int[N];  // 정점 개수만큼 배열 생성
        
        // 모든 원소의 부모를 자기 자신으로 설정
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }
    
    // 특정 원소의 집합(대표자) 찾기 - 경로 압축(Path Compression) 적용
    private static int findSet(int a) {
        if (parents[a] == a) {  // 루트 노드이면 반환
            return a;
        }
        
        // 경로 압축(Path Compression) 적용
        return parents[a] = findSet(parents[a]);  
    }
    
    // 두 개의 집합을 합치기 (유니온)
    private static boolean union(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        
        // 이미 같은 집합이면 합칠 필요 없음
        if (aRoot == bRoot) {
            return false;
        }
        
        // bRoot를 aRoot 아래로 붙임 (간단한 유니온)
        parents[bRoot] = aRoot;
        return true;
    }
    
    public static void main(String[] args) {
        N = 5;  // 정점 개수 5개

        // 1. 집합 생성
        makeSet();
        System.out.println(Arrays.toString(parents));  // 초기 상태 출력

        // 2. 서로 다른 집합 합치기
        System.out.println(union(0, 1));
        System.out.println(Arrays.toString(parents));

        System.out.println(union(2, 1));
        System.out.println(Arrays.toString(parents));

        System.out.println(union(3, 2));
        System.out.println(Arrays.toString(parents));

        System.out.println(union(4, 3));
        System.out.println(Arrays.toString(parents));

        // 3. 특정 정점이 속한 집합의 대표자 찾기
        System.out.println(findSet(1));
    }
}