- 서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미한다.
📌 서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 서로소 집합 자료구조는 두 종류의 연산을 지원한다.
- 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
-
서로소 집합 자료구조는 합치기 찾기 자료구조라고 불리기도 한다.
-
여러 개의 합치기 연산이 주어졌을 때 서로조 집합 자료구조의 동작 과정은 다음과 같다.
- 합집합(Union) 연산을 확인해여 서로 연결된 두 노드 A, B를 확인한다.
1) A와 B의 루트 노드 A', B'을 각각 찾는다.
2) A'을 B'의 부모 노드로 설정한다. - 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복한다.
- 현재 자기 자신의 부모를 자기 자신의 노드 번호로 설정한 배열을 선언한다.
※ 과정을 거쳤을 때 의아한 점이 눈에 띄게 된다. Union(1, 4)을 통해서 {1, 4}가 되고 Union(2, 3)을 통해서 {2, 3}이 되고 Union(2, 4)을 통해서 {2, 4}가 되는데 이 때, 큰 번호의 노드를 작은 번호의 노드의 루트노드로 설정하는게 관행이다. 그랬을 때, 3번 노드의 부모 노드는 2번이 되는데 그렇게 된다면 맞지 않게 된다. 이 때, ★재귀★를 사용한다.
- 서로소 집합 자료구조 : 기본적인 구현 방법
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x): # parent : 부모 테이블, x : 노드의 번호
# 루트 노드를 찾을 때까지 재귀 호출
# 현재 부모가 자기 자신이 아니라면?
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b): # 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))
# 부모 테이블 내용을 출력하기
for i in range(1, v+1):
print(parent[i])
🐢