[알고리즘] [17] 서로소 집합

1. 서로소 집합 (disjoint set)

• 서로소 (상호 배타)집합은 교집합이 없는 집합들이다.
• 집합에 속한 특정 멤버를 통해 각 집합을 구별하며 이를 대표자 (representative)라고 한다.
• 서로소 집합은 연결 리스트 또는 트리로 구현할 수 있다.
• MakeSet, FindSet, UnionSet 연산을 구현한다.

MakeSet(x)

// 유일한 멤버 x를 포함하는 새 집합 생성
MakeSet(x) {
	p[x] <- x;
}

FindSet(x)

// x를 포함하는 집합을 찾는 연산
FindSet(x) {
	if (x == p[x]) return x;
    return FindSet(p[x]);
}

UnionSet(x)

// x와 y를 포함하는 두 집합을 통합하는 연산
UnionSet(x, y) {
	if (FindSet(y) == FindSet(x)) return;
    p[FindSet(y)] <- FindSet(x);
}

 

2. Union Find 최적화

• Rank를 이용한 Union : 두 집합을 합칠 때 rank(depth)가 낮은 집합을 더 높은 집합에 붙인다.
  >> 트리를 이용한 서로소 집합 구현에서 사용
  >> 두 트리의 depth가 동일하다면 합친 후 전체 트리의 depth += 1이다.
  
  
• Path Compression : FindSet 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.
  >> 특정 노드에서 루트까지의 경로를 찾아가며 노드의 부모 정보를 갱신한다.
  >> rank에 변화가 생길 가능성이 존재한다는 문제가 있다.

 

맞는 예시인지 모르겠지만 얼마 전에 푼 SUAPC 대회 문제에서 생각한 아이디어와 유사한 것 같다.

집합을 합치는 과정에서 집합의 조상 노드의 가장 마지막 자식 노드의 번호를 업데이트하며 합쳐주었다.

Path Compression 방식과 유사하지 않나..?

31423번: 신촌 통폐합 계획

[BOJ] [JAVA] 31423번 신촌 통폐합 계획