서로소 집합 알고리즘[파이썬 코드]

서로소 집합이란 공통 원소가 없는 두 집합을 의미.

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

서로소 집합 자료구조의 연산자

• union - 합집합
• find - 찾기

서로소 집합은 연산의 이름을 딴, union-find (어떤 원소를 공통으로 갖는지 찾는다) 자료구조라고 불리기도 한다.

서로소 집합 자료구조는 트리 자료구조를 사용하여 구현.

서로소 집합 계산 알고리즘 수행과정

1. union (합집합) 연산을 확인하여, 서로 연결된 두 노드 a, b를 확인한다.
   • a와 b의 루트 노드 A, B를 각각 찾는다.
   • A, B중 더 작은 원소를 나머지 하나의 원소의 부모 노드가 되도록 한다.
2. 모든 union 연산을 처리할 때까지 1.번 과정을 반복한다.

5개의 원소로 구성된 집합 {1, 2, 3, 4, 5}가 있고 다음과 같은 3개의 union 연산이 주어진 상황을 생각해보겠다.

• union 1, 5
• union 1, 3
• union 2, 4

위의 union연산은 각각 $($1, 5)는 같은 집합, $($1, 3)은 같은 집합, $($2, 4)는 같은 집합이라는 의미와 같다.

union 연산은 두 정점 사이를 연결하는 간선으로도 생각할 수 있다.

따라서 위의 union연산을 그래프로 표현하면 다음과 같다.

step 1.

먼저 노드의 개수 크기의 부모 테이블을 생성하고 인덱스 값을 각자 자신의 노드번호 값으로 초기화 한다.

$($부모 테이블은 각 노드의 부모에 대한 정보만을 저장한다.)

step 2. union$($1, 5)

union 연산을 하여 1과 5를 합친다.

노드 1과 노드 5의 루트 노드$($부모 노드)를 찾으면 된다.

현재 노드 1과 노드 5의 루트 노드는 자기 자신이기 때문에 노드 5의 부모$($5)를 더 작은 루트 노드를 갖는 노드 1의 루트 노드$($1)로 설정한다.

step 3. union$($1, 3)

1과 3을 합친다. 따라서 노드 1과 노드 3의 루트 노드를 각각 찾으면 된다.

$($1, 3)의 루트 노드는 각각 1과 3이기 때문에 노드 3의 부모$($3)을 더 작은 루트 노드를 갖는 노드 1의 루트 노드$($1)로 설정한다.

step 4. union$($2, 4)

2와 4를 합친다. 따라서 노드 2와 노드 4의 루트 노드를 각각 찾으면 된다.

$($2, 4)의 루트 노드는 각각 2와 4이기 때문에 노드 4의 부모$($4)를 더 작은 루트 노드를 갖는 노드 2의 루트 노드$($2)로 설정한다.

이상으로 모든 union 연산을 처리했다. 그래프를 보면 {1, 3, 5}, {2, 4} 두 집합으로 나누어 지는것을 알 수 있다.

서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다.

계속 거슬러 올라가다가 노드 번호와 부모 노드가 같아지는 시점에서 멈추면 해당 노드 번호가 특정 노드의 루트가 된다.

위의 예제에서는 표현되지 않았지만 아래 그림을 보면 이해에 도움이 될 것이다.

서로소 집합 파이썬 코드

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] = parent[a]
    else: parent[a] = parent[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=" ")

서로소 집합 알고리즘 시간복잡도

5개의 노드가 존재하는 상황에서 모두 같은 집합에 속하며 1부터 5까지의 모든 원소가 루트 노드로 1을 가질때, 그림은 노드들이 일렬로 나열된 형태가 된다.

이 경우, 노드 5의 루트 노드 1을 찾기 위해서는 “노드 5 → 노드 4 → 노드 3 → 노드 2 → 노드 1” 순서대로 부모 노드를 거슬러 올라가야 되기 때문에 최대 O$($V)의 시간이 소요된다.

그리고 최대 V-1개의 union연산과 M개의 find 연산이 가능할 때, 시간복잡도는 O$($V + M(1 + log2-M/VV)) 가 된다.