221109 서로소 집합(Disjoint Sets)

서로소(disjoint)

공통으로 포함하는 원소가 없는 두 집합의 관계

서로소 집합 관련 연산

Union : 서로 다른 두 개의 집합을 병합
Find : 원소가 어느 집합에 속해있는지 찾음

서로소 집합의 두 연산을 빗대 Union-Find 자료구조라고도 함

서로소 집합의 구현

1. 집합 생성 및 초기화

parent = new int[n];
Arrays.setAll(parent, i -> i);

2. find 함수
   집합의 구분은 그 집합의 대표적인 원소로 함
   이 대표를 통상적으로 '부모'라고 함

public int findParent( int i) {
    if (parent[i] == i) return i;
    return findParent(parent[i]);
}

3. union 함수
   두 개의 원소를 받고 find 함수를 통해 찾은 부모가 일치하면 합침
   보통 정렬을 한 상태에서 먼저 나오는 쪽을 부모로 설정함