유니온 파인드

서로소 집합

• 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
• 서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용된다.

서로소 집합 자료구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• union(합집합) 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
• find(찾기) 연산은 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 
• 스택과 큐가 각각 push와 pop 연산으로 이루어진 것처럼, 서로소 집합 자료구조는 union과 find 연산으로 구성된다.
• 이 자료구조를 구현할 때는 트리를 이용하여 집합을 표현한다.

 

트리를 이용하여 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다. 

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1. A와 B의 루트노드 A', B'를 각각 찾는다.
   2. A'를 B'의 부모노드로 설정한다. (B'가 A'를 가리키도록 한다.)
2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

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


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

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

# Union 연산 각각 수행
for i in range(e):
    a,b = map(int, input().split())
    union_parent(parent,a,b)

# 각 원소가 속한 집합 출력
for i in range(1,v+1):
    print(find_parent(parent,i), end=' ')
print()

# 부모 테이블 내용 출력
print('부모 테이블: ',end='')
for i in range(1,v+1):
    print(parent[i],end=' ')

• 합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작한다. 최악의 경우 찾기 함수가 모든 노드를 전부 확인하게 되어 시간복잡도가 O(V)가 될 수 있다. 
• 찾기 함수를 최적화하는 방법으로 경로 압축을 이용할 수 있다. → 찾기 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.

 

1-2) 서로소 집합 알고리즘 코드 (개선)

def find_parent(parent,x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]