[알고리즘] Disjoint-set

📚 서로소 집합(Disjoint-sets)

• 서로 중복 포함된 원소가 없는 집합들
• 교집합이 없는 두 개의 집합
• 집합에 속한 특정 멤버를 통해 각 집합들을 구분, 이를 대표자라 함

🎇 핵심 개념들 
1. 대표자 저장 : Union(x, y)
2. 각 요소가 내가 속한 그룹의 대표자를 어떻게 찾을지? : Find-Set(x)

---

상호배타 집합 표현

• 연결 리스트
• 트리

1. Make-Set(x) : 집합 만들기 
2. Union(x, y) : 같은 그룹으로 묶어주기

연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼기
• 각 원소는 집합의 대표원소를 가리키는 링크를 가진다

트리

• 하나의 집합을 하나의 트리로 표현
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다
• 구현과 연산이 더 편하다

# 0 ~ 9
# make set - 집합을 만들어주는 과정
parent = [i for i in range(10)]

# find-set
def find_set(x):
    if parent[x] == x:
        return x

    return find_set(parent[x])

# union
def union(x, y):
    # 1. 이미 같은 집합인지 체크
    x = find_set(x)
    y = find_set(y)

    # 대표자가 같으니 같은 집합이다
    if x == y:
        print('싸이클 발생')
        return

    # 2. 다른 집합이라면 같은 대표자로 수정
    # 문제에서 통일성을 유지하기 위해 대표가 더 작은 값을 가리키도록 함
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

union(0, 1)
union(2, 3)
union(1, 3)
# 이미 같은 집합에 속해 있는 원소를 한 번 더 포함하도록 함
# 싸이클 발생 (어디서 출발해도 서로에게 도착할 수 있음)
union(0, 2)
# 대표자 검색
print(find_set(0))
print(find_set(1))
print(find_set(2))
print(find_set(3))

# 같은 그룹인지 판별
t_x = 0
t_y = 2

if find_set(t_x) == find_set(t_y):
    print(f'{t_x}와 {t_y} 는 같은 집합이네')
else:
    print(f'{t_x}와 {t_y} 는 다른 집합일세')