서로소 집합 자료구조
먼저 서로소 집합이란 공통 원소가 없는 즉, 교집합이 없는 두 집합을 의미한다.
예를 들어 (1,2)와 (2,5)는 서로소 집합이 아니지만 (1,2)와 (4,5)는 서로소 집합이다. 따라서 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 데이터를 처리하기 위한 자료구조를 의미힌다.
stack 자료구조에도 pop과 push 연산이 있듯이, 서로소 집합 자료구조에서도 union과 find라는 연산을 지원한다.
- union(합집합) : 두 집합을 하나로 합치는 연산
- find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
그래서 서로소 집합 자료구조는 union-find 자료구조로도 불린다.
동작 과정
여러 개 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같다.
- union 연산 정보 중 하나를 확인하여, 서로 연결된 두 노드 a, b를 확인하다.
- a와 b 노드의 부모 노드인 A, B를 각각 찾는다.
find 연산- A, B 중 더 작은 원소를 나머지 다른 하나의 원소의 부모 노드가 되도록 한다.
union 연산- 위 과정을 union 연산 정보를 모두 처리할 때까지 반복한다.
아래 예시를 통해 단계별로 동작 수행 과정을 살펴보자.
5개의 원소로 구성된 집합 {1, 2, 3, 4, 5}가 있고 다음과 같은 3개의 union 연산이 주어진 상황을 생각해보겠다.
union(1, 5) union(1, 3) union(2, 4)
위의 union 연산은 각각 노드 1과 5를 합치고, 1과 3을 합치며 2와 4를 합치라는 의미와 같다. 또는 두 정점 사이를 연결하는 간선으로도 생각할 수 있다.
STEP 1
먼저 노드의 개수 크기의 부모 테이블을 생성하고 인덱스 값을 각자 자신의 노드번호 값으로 초기화 한다. ( 여기서 부모 테이블은 각 노드의 부모에 대한 정보만을 저장함을 꼭 숙지 해야한다 ! )
STEP 2 union(1, 5)
1과 5에 대하여 union 연산을 해보자. 먼저 노드 1과 노드 5의 루트 노드 (부모 노드)를 찾는다 ( find ). 현재 노드 1과 노드 5의 루트 노드는 자기 자신이기 때문에 노드 5의 부모(5)를 더 작은 루트 노드를 갖는 노드 1의 루트 노드(1)로 설정한다. ( union )
STEP 3 union(1, 3)
그 다음 연산 정보인 1과 3에 대하여 union 연산을 한다. (1, 3)의 루트 노드는 각각 1과 3이기 때문에 노드 3의 부모(3)을 더 작은 루트 노드를 갖는 노드 1의 루트 노드(1)로 설정한다.
STEP 4 union(2, 4)
그 다음 연산 정보인 2과 4에 대하여 union 연산을 한다. (2, 4)의 루트 노드는 각각 2과 4이기 때문에 노드 4의 부모(4)을 더 작은 루트 노드를 갖는 노드 2의 루트 노드(2)로 설정한다.
이렇게 모든 union 연산을 처리했다. 그래프를 보면 {1, 3, 5}, {2, 4} 두 집합으로 나누어 지는것을 알 수 있다. (부모 노드를 기준으로 가르면 된다)
❗️여기서 서로소 집합을 계산할 때 한 가지 고려해야할 점이 있다. 바로 서로소 집합 알고리즘으로 특정 노드의 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다는 점이다. 계속 거슬러 올라가다가 노드 번호가 부모 노드와 같아지는 시점에서 멈추면 해당 노드 번호가 특정 노드의 루트가 된다.
위 예제에서는 표현되지 않았지만 아래 그림을 보면 이해에 도움이 될 것이다.
3번 노드의 경우 직전 부모 노드 값이 적혀있지만 실제 3번 노트의 루트 노드(=최상위 부모 노드)는 선의 방향을 따라 거슬러 올라가면 1번 임을 알 수 있다.
따라서 이러한 문제를 해결하기 위해(= 부모테이블에 항상 루트 부모 노드만을 갖게 하기 위해) 경로 압축 (Path Compression) 라는 테크닉을 활용하게 되는데, 이는 미리 부모 테이블에 루트 부모 노드 값을 갱신해 두는 것을 의미한다.
경로 압축을 사용하게 되면 부모 테이블은 아래와 같다 (경로압축은 말은 되게 어려워 보이는데 사실 매우 간단한 테크닉이다 😗)
구현 코드
경로 압축을 사용하여 서로소 집합을 구현한 python 코드는 아래와 같다.
v, e = map(int, input().split())
# 부모 테이블 초기화
parent = [0] * (v + 1)
# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
''' union-find '''
# x노드의 루트 노드를 찾아서 반환 즉, 특정 노드가 속한 집합의 부모 노드를 찾는 행위
def find_parent(parent, x):
# 거슬러 올라가다가 노드 번호와 부모 노드가 같아지는 시점이 특정 노드의 루트가 된다.
if parent[x] != x:
# 해당 노드의 루트 노드를 부모 노드로 갱신
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소 a,b 가 속한 집합을 합치기
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
''' '''
# 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=" ")
# 각 원소의 루트 노드를 find를 통해 찾든, 부모 테이블을 출력 하든 그 값은 동일함