[알고리즘] Union-Find 연산(서로소 집합 자료 구조)

※ 사용언어: 파이썬

 

 

개념

Union-Find 연산은 서로소 집합 자료구조를 조작하는 연산이다. 서로소 집합 자료 구조란, 서로소 부분 집합(공통 원소가 없는 두 집합)들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

서로소 부분 집합

 

Union는 같은 집합에 소속될 원소들을 구하는 연산이며, Find를 통해 특정 원소가 어떤 집합에 소속되어 있는지 찾는 연산이다. 

 

Union

알고리즘 로직은 다음과 같다.

1. 노드들의 루트 노드를 저장할 테이블(리스트)를 생성한다.

2. 서로 연결된 A,B를 확인하여, A와 B의 루트(부모) 노드를 찾습니다.

3. 루트 노드를 찾은 후, A의 루트 노드와 B의 루트 노드 중 번호가 작은 쪽이 A, B의 루트 노드가 된다. 

# 1. 루트 배열 만들기
# (노드가 1부터 시작할 경우 +1 해주기)
parent = [ 0 for _ in range(노드개수 + 1)]

# 자신의 루트를 본인 노드 설정 (초기화)
for i in range(0, N+1):
    parent[i] = i
    
def union(parent, A, B):
    # 2. 루트 노드 찾기
    A = 루트_노드_찾기(parent, A)
    B = 루트_노드_찾기(parent, B)
    # 3. 루트 노드 찾은 뒤 작은 노드 번호로 갱신
    if A < B:
        parent[B] = A
    else:
        parent[B] = A

 

Find

알고리즘 로직은 다음과 같다.

1. 노드들의 루트 노드를 저장할 테이블(리스트)을 생성한다.

2. 루트 노드 값이 자기 자신과 같지 않는 경우, 재귀적으로 루트 노드를 찾으러 간다.

예를 들어, 6를 탐색했을 때 루트 노드가 인 경우 4의 루트 노드를 찾는다. 4의 루트 노드가 3이면, 3의 루트 노드를 찾는다. 3의 루트 노드가 3인 경우, 3을 반환한다.

# 1. 루트 배열 만들기
# (노드가 1부터 시작할 경우 +1 해주기)
parent = [ 0 for _ in range(노드개수 + 1)]

# 자신의 루트를 본인 노드 설정 (초기화)
for i in range(0, N+1):
    parent[i] = i
    
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

 

 

사이클 판별

서로소 집합 자료구조는 다양한 알고리즘에서 주로 쓰이며, 대표적으로 사이클 판별에 주로 쓰인다. 앞서 설명한 Union 연산과 Find 연산을 합쳐 사이클의 유무를 쉽게 확인할 수 있다. 알고리즘은 다음과 같다.

1. 간선에 연결된 노드의 루트 노드를 확인한다

2. 루트 노드가 같다 == 사이클 발생 / 루트 노드가 같지 않다 == 사이클 발생 하지 않음

3. 모든 간선에 1~2 스탭을 반복한다.

# 부모 노드 초기화
parent = [0 for _ in range(N+1)]
for i in range(0, N+1):
    parent[i] = i
    
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, A, B):
    A = find(parent, A)
    B = find(parent, B)
    if A < B:
        parent[B] = A
    else:
        parent[B] = A
        
# node에 노드 정보를
# edge에 간선 정보를 넣었다고 가정합니다.

#사이클 유무 체크
cycle = False

for i in range(edge):
    # a, b 가 비교할 노드 값이라고 가정합니다.
    if find(parent, a) == find(parent, b):
        cycle = True
        break
    else:
        union(parent, a, b)

이러한 사이클 판별은 신장 트리에 관련된 문제에서 유용하게 사용됩니다. 신장트리란, 하나의 그래프가 있을 때 모든 노드를 방문(포함) 하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다.

신장트리