[자료구조] Union-find 자료구조 python

[자료구조] Union-find 자료구조 python

 

 

살펴볼 주요 개념:

• Union find란?
• Union find 구현(python)

 

1. Union find란?

 

서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조.

다수의 노드들 중에 연결된 노드를 찾거나 노드들을 합칠 때 사용하는 알고리즘이다.

 

union find는 서로소 집합(disjoint set)을 찾아내는 것에 활용된다.

 

union find와 비슷한 것은 python에서는 set()이 있다. set은 membership 연산(어떤 원소가 집합에 속하는 지를 T/F로 알려주는)과 합집합(union), 교집합(intersection), 여집합(difference) 등의 연산을 제공한다.

 

하지만 파이썬의 set은 hash table을 활용하기 때문에 위의 설명은 적절한 것은 아니다. 그냥 집합 비슷한 것이며, 서로소인 집합을 찾아주는 자료구조로 생각하는 것이 좋겠다.

 

 

Union find의 주요 메소드들은 다음과 같다.

---

• make_set(x) # 집합 만들기
• find(x) # x가 속한 집합의 루트값 리턴
• union(x, y) # 합집합

---

 

2. Union find 구현(python)

# 특정 원소가 속한 집합을 찾기
def find(x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find(parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union(a, b):
    a = find(a)
    b = find(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(a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find(i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')