서로소 집합(Disjoint-set)

make_set()

find_set and paht compressin

📔 서로소 집합(Disjoint-set) 이란

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들( 교집합이 없는 상태 )
• 집합에 속한 하나의 특정 원소를 통해 각각의 집합들을 구분 ( 이를 대표자라고 함 )
• 상호 배타 집합을 표현하는 방법
  • 연결 리스트
    • 같은 집합의 원소들은 하나의 연결리스트로 관리
    • 연결리스트의 맨 앞의 원소를 집합의 대표로 한다
    • 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다
  • 트리
    • 하나의 집합을 트리로 표현
    • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨
• 상호배타 집합 연산
  • make_set(x)
  • find_set(x)
  • union(x,y)

📔 서로소 집합(Disjoint-set) 구현

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


def find_set(x):
    if p[x] == x:
        return x
    else:
        p[x] = find_set(p[x])
        return p[x]


def union(x, y):
    # a와 b의 대표자를 찾음
    px = find_set(x)
    py = find_set(y)
    if rank[px] > rank[py]:
        p[py] = px
    elif rank[py] > rank[px]:
        p[px] = py
    else:
        p[px] = py
        rank[py] += 1


# 1부터 8까지 해보자
n = 8
p = [0] * (n + 1)
rank = [0] * (n + 1)
for i in range(1, n + 1):
    make_set(i)

union(1, 3)
union(2, 3)
union(5, 6)
union(6, 8)
union(1, 5)
union(6, 7)
print(p)
print(find_set(4))
print(find_set(5))

# 연산의 효율을 높이는 방법
# 1. path compression: 모든 노드들이 직접 root를 가리키도록 갱신한다.
# 2. Rank를 이용한 Union: 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank라는 이름으로 저장한다.
# 2-2. 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.

 

📔 서로소 집합(Disjoint-set) 특징

• 합집합을 찾을 때 사용
• 여러 개의 노드가 존재할 때 두개의 노드를 선택해서, 선택한 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘