[Python] 서로소 집합(disjoint set) 알고리즘 알아보기
서로소 집합 개념
서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
아래의 그림으로 예시를 알아보자
(가)에서는 집합이 총 2개가 있으며, {1, 2}와 {3, 4}의 원소를 갖고 있다. 두 집합에서 원소가 겹치는 경우가 없기 때문에, 서로소 관계라고 할 수 있다.
반면, (나)의 경우, {1, 2, 4}, {3, 4}의 두 집합이 있으며, 4라는 원소가 두 집합에 공존하고 있기 때문에 서로소 집합 관계가 아니라고 할 수 있다.
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.
이 때, 서로소 집합 자료구조는 union과 find의 2개의 연산으로 조작할 수 있다.
| 연산 명 | 작동 방식 |
| union | 두 집합을 하나의 집합으로 합치는 연산 |
| find | 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 |
서로소 집합은 합집합과 찾기 연산으로 작동된다.
서로소 집합 계산 알고리즘
- union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 루트노드 A', B'를 각각 찾는다.
- A'를 B'의 부모노드로 설정한다. (B'가 A'를 가리키도록 한다.)
- 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.
서로소 집합 계산 알고리즘 예시
집합 {1, 2, 3, 4, 5, 6}이 6개의 원소로 구성되어 있다고 보자, 그리고 다음 아래의 4개의 union 연산이 주어진다.
- union 1, 4
- union 2, 3
- union 2, 4
- union 5, 6
이러한 4개의 union 연산은 각각 1, 4가 같은 집합, 2와 3은 같은 집합 등, 서로 두 원소가 같은 집합에 포함되어 있다는 의미를 지니고 있다. 이 때 4개의 union 연산이 수행된 후에, 전체 원소들이 어떠한 부분집합으로 나누어질지 알아보면 좋다.
위의 합집합 연산을 거친 경우, {1, 2, 3, 4}와 {5, 6}의 총 2개의 부분집합으로 분리될 것이다.
1. 초기 상태
초기 상태는 위와같이 될 것이다. 각 노드의 번호와 부모노드는 각자 자신을 가리키도록하고, union 연산을 하나씩 확인한다.
2. union 1, 4
첫 연산을 통해 1과 4번 노드를 합쳐준다. 이 때, 노드 1과 노드 4의 루트노드를 찾으면 되며, 보통 연산에서 부모노드는 번호가 앞서는 노드로 지정하기에, 4번 노드의 부모노드를 1번으로 변경해준다.
3. union 2, 3
현재 union 연산을 확인하면 2와 3을 합치게 된다. 동일하게 3번 노드의 부모노드를 2번으로 바꿔준다.
4. union 2, 4
다시 union 연산을 하게 되면 2와 4를 합치게 된다.
여기서 헷갈리면 안되는데, 각각의 루트노드를 확인해주면 1번과 2번 노드가 나오게 된다. (4번의 루트노드가 1번)
따라서 기존 법치겡 의거, 작은 숫자를 지닌 1번 노드를 부모노드로 지정하며 2번의 부모노드가 1번으로 지정된다.
5. union 5, 6
마지막으로 두 5와 6을 합쳐주면, 6번의 부모노드가 5번으로 갱신된다.
이상으로 앞선 모든 합집합 연산을 처리했다.
물론 3번노드의 최종 부모노드는 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위 두 함수를 통해 재귀적으로 부모 노드를 찾고, 속한 집합을 합쳐주는 union 연산을 수행한다.
main함수 바디 부분은 아래와 같으며, 간선 정보는 union 연산으로 이해하여 봐주면 된다.
- main 함수 부분
# 노드의 개수와 간선(union 연산)의 개수 입력
v, e = map(int, input().split())
# 부모 테이블 상에서 부모를 자기 자신으로 초기화
parent = [i for i in range(v+1)]
# 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=' ')
예시와 같은 데이터를 입력해보자
아래와 같은 입력문을 넣으면 출력은 우리가 계산한 것과 동일하게 나와줄 것이다.
- 입력문
6 4
1 4
2 3
2 4
5 6
- 출력문
각 원소가 속한 집합 : 1 1 1 1 5 5
부모 테이블 : 1 1 2 1 5 5
위와같은 알고리즘을 통해 서로조 집합을 계산하고, 각 원소가 속한 집합의 번호를 알아낼 수 있었다.
여기서 작성하면서 알 수 있었을텐데, find_parent함수가 비효율적으로 나오게 되어 있다.
union 연산을 수행하는 과정에서 매번 find_parent 함수를 호출하게 되는데, 재귀가 계속 돌면서 많은 시간을 소요하게 된다. 이때는, DP와 같은 방식으로 사용되는 memorizing 기법을 사용해주면 되는데, 이를 경로압축 기법이라고 한다.
- 경로압축 기법 find_parent
# 경로압축 기법
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
위와 같은 방식으로 수정하면, 한 번 각 노드에 대하여, find 함수 호출 시, 해당 노드의 루트노드가 바로 부모노드가 되어 버린다. 그렇게 되면 매번 재귀적으로 계산해야했던 이전과 달리, 시간복잡도가 매우 개선된 것을 알 수 있다.
서로소 집합 계산 알고리즘 시간복잡도
서로소 집합 알고리즘을 구현할 때의 시간복잡도는 아래와 같이 계산할 수 있다.
노드의 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때, 시간복잡도는
위 수식과 같다.
대략 find 및 union 연산이 총 100만번 수행된다고 하면, 약 1000만 번 정도의 연산이 필요하게 된다고 이해하면 된다.