서로소 집합(Disjoint sets; 상호배타집합)

서로소 집합의 개념

 

서로 중복 포함된 원소가 없는 집합들로서 즉, 교집합이 없는 집합이다. 집합에 속한 하나의 특정 멤버를 통해(→ 대표자; 대표자는 딱 하나 존재한다) 각 집합들을 구분한다. 특정 원소의 대표자를 가져왔을 때 동일하면 같은 집합에 속해있다고 판단할 수 있다. 

 

 

Union-Find의 개념

 

서로소 집합을 표편할 때 사용하는 알고리즘으로서 트리를 이용해 구현 가능

; 그밖에 비트 벡터, 배열, 연결리스트를 이용해서도 구현 가능

 

 

Union-Find의 연산

 

연산1) Make-Set(x): 집합 생성 역할(x라는 원소를 대표자로 만든다)

연산2) Find-Set (x): x의 대표자를 가져오는 역할 (부모가 아님)

연산3) Union(x, y): x와 y 두개의 원소를 하나의 그룹으로 만드는 역할

→ Union을 하기 위한 전제조건: 대표자인 원소로만 union할 수 있다.
→ 따라서 union의 매개변수가 대표가 아닌 원소가 왔다면 대표 원소를 찾아서 처리
→ 유니언 한 후 대표는 코드 구현에 따라 정해진다.

Union-Find의 연산 효율 증대

 

여러번 find-set를 수행한다면 중복된 호출이 발생하고 편향 트리인 경우 시간 소요가 크다는 단점이 있다. 따라서 다음과 같은 방법을 활용해 연산의 효율을 높일 수 있다.

 

1) rank 활용하기

각 노드는 자신을 루트로 하는 서브 트리의 높이를 rank라는 필드로 저장한다.
두 집합을 합칠 때 rank가 낮은 집합을 높은 집합에 붙인다. => 높이 변화 일어나지 않음
* 두 집합의 높이가 같은 경우에는 높이++ 해준다.

 

2) path compression 활용하기

Find-Set 과정에서 대상이 되는 모든 노드가 직접 root를 가리키도록 포인터 바꾸기