[CS기초] 서로소 집합(Disjoint Sets) 알고리즘 - Union, Find

서로소 집합

서로소 집합(Disjoint Sets)이란?

서로소 집합 자료구조란 공통 원소가 없는 서로소 부분 집합들로 나누어진 데이터를 효율적으로 처리하기 위한 자료구조입니다. 예를 들어, 집합 {1, 2}와 {3, 4}는 서로소 관계이지만, 집합 {1, 2}와 {2, 3}은 공통 원소인 2를 포함하기 때문에 서로소가 아니라고 할 수 있습니다.

 

 

주요 연산

서로소 집합 자료구조는 두 가지 핵심 연산으로 이루어집니다.

• 합치기(union): 두 원소가 포함된 집합을 하나로 합치는 연산
• 찾기(find): 특정 원소가 어떤 집합에 속해 있는지 알려주는 연산

이 두 연산 덕분에 서로소 집합 자료구조는 Union-Find 자료구조라고도 불립니다.

 

 

서로소 집합 알고리즘의 동작과정

서로소 집합 자료구조는 주로 트리 자료구조를 이용해 집합을 표현합니다. 구체적인 구현 과정은 다음과 같습니다:

1. 합치기(union) 연산으로 연결된 두 노드(A, B)를 확인한다.
2. 각 노드의 루트 노드(A', B')를 찾기(find) 연산으로 구한다.
3. 두 루트 노드 중 더 작은 값을 가진 노드를 다른 노드의 부모로 설정한다.
4. 모든 합치기 연산을 처리할 때까지 위 과정을 반복한다.

 

서로소 집합 알고리즘의 시간 복잡도

서로소 집합 알고리즘을 구현할 때, find 함수를 재귀적으로 호출한 뒤 부모 테이블값을 갱신하는 기법인 경로 압축을 이용할 수 있습니다. 이 경우 노드의 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때의 시간 복잡도를 알아보면 다음과 같습니다.

 

예를 들어, 노드의 개수가 1000개이고, 총 연산 횟수가 100만 번이더라도, 전체 연산은 매우 적은 시간 안에 처리될 수 있습니다.

 

 

서로소 집합을 활용한 사이클 판별

서로소 집합은 특히 무방향 그래프의 사이클 판별에 유용하게 사용됩니다. 간선을 통해 연결된 노드들이 서로 다른 집합에 있는지를 확인하는 것으로 사이클 여부를 쉽게 판단할 수 있습니다.

 

동작 과정은 다음과 같습니다.

1. 각 간선을 하나씩 확인하면서 두 노드의 루트 노드를 찾는다.
   1. 루트 노드가 서로 다르면 두 노드를 합집합 연산으로 연결한다.
   2. 루트 노드가 같다면 사이클이 존재하는 것이므로 판별을 종료한다.
2. 모든 간선에 대해 위 과정을 반복하여 사이클 여부를 판별한다.

 

파이썬에서 서로소 집합 알고리즘의 구현

# find: 특정 원소가 속한 루트 노드를 찾는 함수 (경로 압축 적용)
def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

# union: 두 원소가 속한 집합을 합치는 함수 (작은 번호가 부모가 되도록 설정)
def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기    
v, e = map(int, input().split())
parent = [0] * (v+1)    # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
    parent[i] = i

cycle = False   # 사이클 발생 여부

# 모든 간선에 대해 union 연산 수행
for _ in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(a) == find_parent(b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(union) 수행
    else:
        union_parent(a, b)

# 사이클이 발생한 경우 해당 문구 출력
if cycle:
    print("사이클이 발생했습니다.")
# 사이클이 발생하지 않은 경우 각 원소의 루트 노드 출력
else:
    print('각 원소의 루트 노드: ', end='')
    for i in range(1, v+1):
        print(find_parent(i), end=' ')