1. 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조입니다.
2. 서로소 집합 자료구조는 두 종류의 연산을 지원합니다.
2.1 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산입니다.
2.2 찾기(Find) : 특성한 원소가 속한 집합이 어떤 집합인지 알려주는 연산입니다.
3. 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고도 불립니다.
여러개 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 아래와 같습니다.
1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인합니다.
1) A와 B 루트 노드 A`, B`를 각각 찾습니다.
2) A`를 B`의 부모 노드로 설정합니다. (단, A가 B보다 작을 때)
2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복합니다.
처리할 연산들 : Union(1,4), Union(2,3), Union(2,4), Union(5,6)
[초기 단계] 노드의 개수 크기의 부모 테이블을 초기화합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 3 | 4 | 5 | 6 |
[Step 1] Union(1,4)를 처리합니다. 노드 1과 노드 4의 루트 노드를 각각 찾습니다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 노드 4의 부모를 1로 설정합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 3 | 1 | 5 | 6 |
[Step 2] Union(2,3)을 처리합니다. 노드 2와 노드 3의 부모 노드를 찾습니다. 현재 부모 노드는 각각 2와 3이므로 더 큰 번호에 해당하는 노드 3의 부모를 2로 설정합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 2 | 1 | 5 | 6 |
[Step 3] Union(2,4)을 처리합니다. 노드 2와 노드 4의 부모 노드를 찾습니다. 현재 부모 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 노드 2의 부모를 1로 설정합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 1 | 2 | 1 | 5 | 6 |
여기서 노드 3과 노드4를 확인했을 때 노드4의 부모노드는 1이고 노드 3의 부모노드는 2이며, 노드 2의 부모 노드는 1이므로 결국 같은 집합에 포함되어 있는 것으로 처리할 수 있습니다.
[Step 3] Union(5,6)을 처리합니다. 노드 5와 노드 6의 부모 노드를 찾습니다. 현재 부모 노드는 각각 5와 6이므로 더 큰 번호에 해당하는 노드 6의 부모를 5로 설정합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 1 | 2 | 1 | 5 | 5 |
마지막으로, 각 노드의 집합구조는 아래와 같이 구성되며 [1,2,3,4]와 [5,6]은 서로소 관계인 것을 확인할 수 있습니다.
# 특성 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드를 찾을 때까지 재귀 호출 (부모의 루트 노드 탐색)
if parent[x] != x:
parent[x] = find_parent(parent, parent[x]) # 경로 압축
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a) # a 노드의 부모 노드 찾기
b = find_parent(parent, b) # 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
# Union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
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= ' ')