[Algorithm] 서로소(상호배타) 집합 (Disjoint-sets)

서로소(상호배타) 집합

• 서로 중복 포함된 원소가 없는 집합
• 교집합이 없음
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분 → 대표자(representative)

 

상호배타 집합 표현 - 트리

• 하나의 집합을 하나의 트리로 표현
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨

 

상호배타 집합 연산

nodes = [1, 2, 3, 4, 5, 6]
parents = [0] * (len(nodes) + 1) # 각 노드의 부모를 저장할 배열

• Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성

def make_set(x):
    parents[x] = x
    

for node in nodes:
    make_set(node)

• Find-Set(x) : x를 포함하는 집합을 찾는 연산, 대표자를 반환

def find_set(x):
    if x == parents[x]:
        return x

    return find_set(parents[x])

• Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산

# 1) 두 집합의 대표자를 찾아서
# 2) 한 쪽의 대표자를 반대쪽의 대표자 바로 밑에 붙이기
def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    # 대표자가 같을 경우 이미 같은 집합에 속해있음
    if root_x == root_y:
        return False

    parents[root_y] = root_x
    return True

→ 이와 같이 구현하는 경우, union 연산 시 트리의 깊이가 계속해서 깊어짐

 

[연산의 효율 높이기]

1. Rank를 이용한 Union
   • 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank로 저장
   • 두 집합을 합칠 때 Rank가 낮은 집합을 Rank가 높은 집합에 붙임
2. Path compression
   • Find-set을 행하는 과정에서 만나는 모든 노드들이 루트를 직접 가리키도록 포인터를 바꾸어줌

nodes = [1, 2, 3, 4, 5, 6]
parents = [0] * (len(nodes) + 1)
ranks = [0] * (len(nodes) + 1)

def make_set(x):
    parents[x] = x
    ranks[x] = 0


def find_set(x):
    """
    path compression 적용
    => 부모 노드를 루트 노드로 갱신
    """
    if x != parents[x]:
        parents[x] = find_set(parents[x])

    return parents[x]


def union(x, y):
    """
    union by rank 적용
    => rank 값이 더 큰 쪽에 붙이기
    """
    root_x = find_set(x)
    root_y = find_set(y)

    # root_x의 트리의 높이(rank)가 더 크거나 같을 경우
    if ranks[root_x] > ranks[root_y]:
        parents[root_y] = root_x
        # 만약에 높이가 같다면 rank 증가
        if ranks[root_x] == ranks[root_y]:
            ranks[root_x] += 1
    # root_y의 트리의 높이가 더 클 경우
    else:
        parents[root_x] = root_y