공통 원소가 없는 두 집합
e.g. {1,2} {3,4} -> 서로소 관계임 {1,2} {2,3} -> 서로소 관계가 아님
서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
-> 연산 : union + find
2개 원소로 이루어진 집합을 하나의 집합으로 합치기
특정 원소가 속한 집합이 뭔지 알려주는 연산
-> 서로소 집합 자료구조는 union + find 연산으로 구성되므로 union-find 자료구조라고 불리기도 함
e.g.
{1,2,3,4,5,6}의 집합과 4개의 union 연산 union 1,4 union 2,3 union 2,4 union 5,6이 주어졌다.
이를 그래프로 표현하면,
위와 같이 구성됨을 알 수 있다.
이를 완성하기 위한 구체적인 알고리즘 동작 방법은 아래와 같다.
부모 테이블 초기화
노드의 개수 크기의 부모 테이블을 초기화 한다. 초기값은 자기 자신을 부모로 가지도록 설정한다.
노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
부모 | 1 | 2 | 3 | 4 | 5 | 6 |
각각의 union 연산을 확인한다. -> union 1,4
1과 4의 루트노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호인 루트 노드 4의 부모를 1로 설정
노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
부모 | 1 | 2 | 3 | 1 | 5 | 6 |
union 2,3
노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
부모 | 1 | 2 | 2 | 1 | 5 | 6 |
union 1,2
노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
부모 | 1 | 1 | 2 | 1 | 5 | 6 |
union 5,6
노드번호 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
부모 | 1 | 1 | 2 | 1 | 5 | 5 |
-> 모든 union 연산을 수행한 결과
코드로 구현하면 아래와 같다.
# 특정 원소가 속한 집합을 찾기
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)
# 각 원소가 속한 집합 출력하기
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=' ')
{1,2,3,4,5}의 집합에서 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 총 의 시간이 소요된다. 결과적으로 위의 find 함수를 그대로 사용하면 노드의 개수 V개, union나 find 연산의 개수 M개라고 할때 최악의 경우 의 시간이 소요된다.
경로 압축을 이용해서 최적화를 할 수 있다. find 함수를
# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
return find_parent(parent, parent[x])
return parent[x]
와 같이 리턴값만 parent[x]
로 수정해주면 된다.
개선된 알고리즘으로 위의 예제를 수행하면,
노드번호 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
부모 | 1 | 1 | 1 | 1 | 1 |
부모 테이블이 위와 같아지고, 루트노드에 더 빠르게 접근할 수 있다.
경로압축 방법을 사용한 결과의 시간 복잡도는 아래와 같다.
노드의 개수V개, 최대 V-1개의 union 연산과 M개의 find 연산을 수행할 때 시간복잡도는
유니온파인드 알고리즘을 이용해서 무방향 그래프 내에서 사이클을 판별할 수 있다.
소스코드로 나타내면 아래와 같다
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else:
union_parent(parent, a, b)
좋은 글 감사드립니다. 다름이 아니라 질문이 하나 있어서 댓글 남깁니다:) find_parent 경로 압축에서 부모 테이블을 바꾸기 위해서는 parent[x]=find(parent,parent[x])부분이 있고, 그래프 union연산 순서가 오름차순(parent가 먼저 union을 거치도록)으로 되어 있거나 union 연산들을 진행 후에 parent[parent[x]]와 parent[x]가 다른 값이 있으면 업데이트해주는 과정을 필요로 하는 것이 아닌지 여쭈어보고 싶습니다.
추가적으로 parent 리스트가 함수 밖에서 정의되어 있는데 input parameter로 계속 넣어주어야 할 필요성이 있을지 여쭈어보고 싶습니다.
감사합니다.
잘 봤습니다~