서로소 집합(Disjoint Sets) [Python / 파이썬]

1. 서로소 집합이란?

수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다.

예를 들어 집합 {1, 2}와 {3, 4}는 서로소 관계이다. 반면 집합 {1, 2}와 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다.

서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다.

union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다.

예를 들어 전체 집합{1, 2, 3, 4, 5, 6}에서 서로소 부분집합이 다음과 같이 주어진다고 가정하자.

{1, 4}, {2, 3}, {2, 4}, {5, 6} 이와 같이 주어진 서로소 부분집합들은 각각 동일한 서로소 집합에 포함되어있는 원소들이다.

위와 같은 부분 집합들을 서로소 집합 자료구조를 통해 각 원소들의 서로소 집합을 알아낼 수 있는데

위와 같은 서로소 부분 집합은 union연산을 통해 서로소 집합을 알아낼 수 있다. 필요한 union연산은 아래와 같다.

union 1, 4
union 2, 3
union 2, 4
union 5, 6

위의 union연산의 의미는 다음과 같다.

1과 4는 동일한 서로소 집합
2와 3는 동일한 서로소 집합
2와 4는 동일한 서로소 집합
5와 6는 동일한 서로소 집합

2. 서로소 집합의 형태

위의 예시에 대한 union 연산을 수행했을 때의 결과를 트리 구조로 표현하면 아래와 같다.

트리 자료구조는 root 노드를 가지므로 각 원소의 root 노드를 확인함으로써 동일한 집합임을 확인할 수 있다.

3. 서로소 집합의 구현

그렇다면 서로소 부분집합이 주어졌을때 서로소 집합을 구현하는 방법을 알아보자.

step0 초기 단계에서는 가장 먼저 노드의 개수(V) 크기의 부모 테이블을 초기화한다. 이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다. 현재 원소의 개수가 6이므로, 초기 단계에서는 총 6개의 트리가 존재하는 것과 같다. 여기서 부모 테이블은 특정 노드의 부모에 대해서 저장하고 있다. 실제로 루트를 확인하고자 할 때는 재귀적으로 부모를 거슬러 올라가서 최종적인 루트 노드를 찾아야 한다.

노드 번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

step1 union 1, 4

첫 번째 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

첫 번째 union 연산을 확인하면, 2와 3을 합친다. 이때는 노드 2와 노드 3의 루트 노드를 각각 찾으면 된다. 현재 루트 노드는 각각 2와 3이기 때문에 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.

노드 번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

step3 union 2, 4

첫 번째 union 연산을 확인하면, 2와 4를 합친다. 이때는 노드 2와 노드 4의 루트 노드를 각각 찾으면 된다. 현재 2와 4의 루트 노드는 각각 2와 1이기 때문에 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.

노드 번호	1	2	3	4	5	6
부모	1	1	2	1	5	6

step3 union 5, 6

첫 번째 union 연산을 확인하면, 5와 6을 합친다. 이때는 노드 5와 노드 6의 루트 노드를 각각 찾으면 된다. 현재 5와 6의 루트 노드는 각각 5와 6이기 때문에 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정한다.

노드 번호	1	2	3	4	5	6
부모	1	1	2	1	5	5

이상으로 모든 union 연산을 처리했다. 이 알고리즘에서 유의할 점은 union 연산을 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 한다는 점이다.

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 연산)의 개수 입력 받기
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(f'node {i} in {find_parent(parent, i)}')
    
# 부모 테이블 출력
for i in range(1, v + 1):
    print(f'node {i}s parent is {parent[i]}')

4. 경로 압축 기법

위와 같이 find함수를 구현 하였을때 최악의 경우 find 함수가 모든 노드를 다 확인하는 터라 시간 복잡도가 O(V)가 된다. 다음과 같이 {1, 2, 3, 4, 5}의 총 5개의 원소가 존재하는 상황에서 모두 같은 집합에 속하는 경우를 가정해보자.

구체적으로 4개의 union 연산이 순서대로 (4, 5), (3, 4), (2, 3), (1, 2)와 같이 주어졌다고 해보자. 이때 차례대로 연산을 처리하게 되면 다음과 같이 일열로 나열하는 형태가 된다.

노드 번호	1	2	3	4	5
부모	1	1	2	3	4

예를 들어 노드 5의 루트를 찾기 위해서는 '노드 5 → 노드 4 → 노드 3 → 노드 2 → 노드 1' 순서대로 부모 노드를 거슬러 올라가야하므로 최대 O(V)의 시간이 소요될 수 있다. 결과적으로 현재의 알고리즘을 그대로 이용하게 되면 노드의 수가 V개이고 find 혹은 union 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적이다.

하지만 이러한 find 함수는 아주 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있다.

아래와 같이 find함수를 수행하고 부모 테이블을 갱신 시켜주면 된다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

결과적으로 경로 압축 기법을 이용하게 되면 루트 노드에 더욱 빠르게 접근할 수 있다는 점에서 기존의 기본적인 알고리즘과 비교했을 때 시간 복잡도가 개선된다.

노드 번호	1	2	3	4	5
부모	1	1	1	1	1

4.1 경로 압축 기법을 사용한 구현 소스 코드

# 특정 원소가 속한 집합을 찾기
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)
    b = find_parent(parent, 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)
    
# 각 원소가 속한 집합 출력
for i in range(1, v + 1):
    print(f'node {i} in {find_parent(parent, i)}')
    
# 부모 테이블 출력
for i in range(1, v + 1):
    print(f'node {i}s parent is {parent[i]}')

Deeppago's study note