[알고리즘] 서로소 집합 자료구조

서로소 집합 자료구조

서로소 집합

• 공통 원소가 없는 두 집합을 의미

서로소 집합 자료구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 두 종류의 연산 지원
  - 합집합: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  • 찾기: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 합치기 찾기(Union Find) 자료구조라고 불리기도 함

여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정
1. 합집합 연산을 확인하여 서로 연결된 두 노드 A, B 확인
- 1) A와 B의 루트 노드 A', B'를 각각 찾음
- 2) A'를 B'의 부모 노드로 설정
2. 모든 합집합 연산을 처리할 때까지 1번 반복

• 부모를 자기 자신으로 설정 (모두 각각 다른 집합으로 생각)

• 일반적으로 더 큰 루트 노드가 더 작은 루트 노드를 가르키도록 만들어서 테이블을 갱신하는 것이 보통

• 2번의 노드는 2번이었는데 1로 바뀜
• 현재 이 테이블은 부모 노드에 대해서 기록하는 테이블임을 인지
• 3번과 4번은 부모가 다름 -> 3번을 보고 2번이 부모임을, 2번을 보고 1번이 부모임을 알아야 함 -> 둘 다 부모가 1이므로 루트 노드가 같음
  -> 루트 테이블이 아닌 부모 테이블임을 유의

특징

• 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없음
  - 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 함

코드 구현

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:  # 부모가 자기 자신이 아니라면 루트 노드가 아님
        return find_parent(parent, parent[x]) # 부모 노드 번호를 넣어서 다시 호출
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b): # 루트 번호를 찾은 뒤 번호 확인
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b: # 더 번호가 큰 쪽이 작은 쪽을 부모로 설정
        parent[b] = a
    else:
        parent[a] = b

---

문제점

• 합집합 연산이 편향되게 이루어지는 경우 찾기 함수가 비효율적
• 최악의 경우에는 찾기 함수가 모든 노드 확인 -> O(V)

찾기 함수 최적화를 위한 경로 압축 방법 사용 가능

• 찾기 함수 재귀적으로 호출한 뒤 부모 테이블 값 바로 갱신

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x