자료 구조 (7) : 유니온 파인드(Union Find)

유니온 파인드, 서로소 집합

여러 개의 원소가 있을 때, 그 원소들이 어떤 집합에 속하는지 효율적으로 관리하기 위한 자료 구조

 

• 주요 연산
  • find(x) : 원소 x가 속한 집합의 대표를 찾는 연산으로, 원소 x가 어느 집합에 속해 있는지 찾는 데 사용
  • union(x, y) : 원소 x와 원소 y가 속한 집합을 합치는 연산
• 사용 상황(같은 집합 내 연산)
  • 최소 스패닝 트리(크루스칼 알고리즘)
  • 최소 공통 조상
  • 네트워크 연결 확인
• 연산 최적화
  • find(x) : find(x) 수행 시, 지나간 모든 노드가 직접 루트 노드를 가리키도록 변경
  • union(x, y) : 높이가 낮은(크기가 작은) 집합을 높이가 높은(크기가 큰) 집합에 병합
  • 연산 최적화를 적용해야 유니온 파인드 대부분 연산의 시간 복잡도가 O(α(N))

* α(N) 시간 복잡도는 상수 시간에 가까운 아주 빠른 시간복잡도

• 시간 복잡도

	연산 최적화한 유니온 파인드
생성	O(logN)
Union	O(α(N))
Find	O(α(N))
크기(Size)	O(α(N))
연결 확인(connected)	O(α(N))

 

* α(N) 시간 복잡도는 상수 시간(O(1))에 가까운 아주 빠른 시간복잡도

 

Union-Find 구현 예시

 

public class UnionFind {

    private int size;
    private int[] sizes;
    private int[] parent;

    private int dsuCnt;

    public UnionFind(int size) {

        if (size <= 0) throw new IllegalArgumentException("크기는 0보다 커야 합니다");

        this.size = dsuCnt = size;
        sizes = new int[size];
        parent = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            sizes[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int componentSize(int x) {
        return sizes[find(x)];
    }

    public int size() {
        return size;
    }

    public int components() {
        return dsuCnt;
    }

    public void union(int x, int y) {

        if (connected(x, y)) return;

        int root1 = find(x);
        int root2 = find(y);

        if (sizes[root1] < sizes[root2]) {
            sizes[root2] += sizes[root1];
            parent[root1] = root2;
            sizes[root1] = 0;
        } else {
            sizes[root1] += sizes[root2];
            parent[root2] = root1;
            sizes[root2] = 0;
        }

        dsuCnt--;
    }
}