서로소 집합 자료구조(Disjoint Sets)
개념
: 공통 원소가 없는 두 집합인 '서로소 부분 집합'들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
-
트리 자료구조를 이용하여 집합 표현
-
union-find 자료구조로도 불림
-
루트 노드를 찾기 위해서는 재귀적으로 부모 노드를 거슬러 올라가야 함
연산
1. UNION (합집합 연산)
: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- 간접적으로 연결되어 이동할 수 있는 노드들에 대해서도, 같은 집합에 있는 것으로 이해할 수 있다.
2. FIND (찾기 연산)
: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
서로소 집합 계산 알고리즘
개념
: 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘
동작 원리
-
노드의 개수
V크기의 부모 테이블을 초기화 한다. 이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다. -
union(합집합) 연산을 확인하여, 서로 연결된 두 노드
A,B를 확인한다. -
A와B의 루트 노드인A'과B'을 각각 찾는다. -
A'를B'의 부모 노드로 설정한다. (B'가A'을 가리키도록 한다.)
(✓ 보통은 번호가 작은 원소가 부모 노드가 되도록 설정한다.)
(✓ '가리킨다' : 부모 노드로 설정한다는 의미) -
모든 union(합집합) 연산을 처리할 때 까지 1 ~ 3번의 과정을 반복한다.
예를 들어 6개의 원소로 구성된 전체 집합 {1, 2, 3, 4, 5, 6}이 있고, 다음의 4개의 union 연산이 주어져 있다고 생각해보자.
- union 1, 4
- union 2, 3
- union 2, 4
- union 5, 6
소스코드
# 특정 원소가 속한 집합 찾는 함수 정의
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()) # v: 노드 개수, e: 간선 개수(union 연산 개수)
parent = [0] * (v+1) # 부모 테이블 (0으로 초기화)
# 초기상태 : 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# union 연산 각각 수행
for i in range(e):
a, b = map(int, input().split()) # 서로 같은 집합에 있는 원소 a, b 입력 받기
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end = ' ')
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 = ' ')6 4
1 4
2 3
2 4
5 6
각 원소가 속한 집합: 1 1 1 1 5 5
부모 테이블: 1 1 2 1 5 5
🔗 References
벌집처럼 밀도있게 차곡차곡 쌓아나가는중