[알고리즘] union-find 알고리즘

김우경·2021년 1월 19일
3

수학에서의 서로소 집합

공통 원소가 없는 두 집합
e.g. {1,2} {3,4} -> 서로소 관계임 {1,2} {2,3} -> 서로소 관계가 아님

서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
-> 연산 : union + find

union

2개 원소로 이루어진 집합을 하나의 집합으로 합치기

find

특정 원소가 속한 집합이 뭔지 알려주는 연산

-> 서로소 집합 자료구조는 union + find 연산으로 구성되므로 union-find 자료구조라고 불리기도 함

서로소 집합 계산 알고리즘

동작 방법

  1. union 연산 확인
    : 서로 연결된 두 노드를 확인
    1.1 A의 루트 노드 A'과 B의 루트 노드 B'를 찾기 (find)
    1.2 A'를 B'의 부모 노드로 설정 (A' < B')
  2. 모든 union 연산을 처리할 때까지 1 반복

e.g.
{1,2,3,4,5,6}의 집합과 4개의 union 연산 union 1,4 union 2,3 union 2,4 union 5,6이 주어졌다.
이를 그래프로 표현하면,

위와 같이 구성됨을 알 수 있다.

이를 완성하기 위한 구체적인 알고리즘 동작 방법은 아래와 같다.

  1. 부모 테이블 초기화
    노드의 개수 크기의 부모 테이블을 초기화 한다. 초기값은 자기 자신을 부모로 가지도록 설정한다.

    노드번호123456
    부모123456
  2. 각각의 union 연산을 확인한다. -> union 1,4
    1과 4의 루트노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호인 루트 노드 4의 부모를 1로 설정

    노드번호123456
    부모123156
  3. union 2,3

    노드번호123456
    부모122156
  4. union 1,2

    노드번호123456
    부모112156
  5. union 5,6

    노드번호123456
    부모112155

-> 모든 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=' ')

문제점 : 비효율적인 find 함수

{1,2,3,4,5}의 집합에서 union 연산이 (4,5), (3,4), (2,3), (1,2)와 같다고 할때, 부모테이블은 다음과 같아진다.

노드번호12345
부모11234

이 경우 5의 루트노드를 찾기 위해서는 5->4->3->2->1 총 O(V)O(V)의 시간이 소요된다. 결과적으로 위의 find 함수를 그대로 사용하면 노드의 개수 V개, union나 find 연산의 개수 M개라고 할때 최악의 경우 O(VM)O(VM)의 시간이 소요된다.

개선된 서로소 집합 알고리즘

경로 압축을 이용해서 최적화를 할 수 있다. find 함수를

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

와 같이 리턴값만 parent[x]로 수정해주면 된다.

개선된 알고리즘으로 위의 예제를 수행하면,

노드번호12345
부모11111

부모 테이블이 위와 같아지고, 루트노드에 더 빠르게 접근할 수 있다.

시간 복잡도

경로압축 방법을 사용한 결과의 시간 복잡도는 아래와 같다.
노드의 개수V개, 최대 V-1개의 union 연산M개의 find 연산을 수행할 때 시간복잡도는

O(V+M(1+log2M/V/V))O(V+M(1+log_{2-M/V}/V))

사이클 판별법

유니온파인드 알고리즘을 이용해서 무방향 그래프 내에서 사이클을 판별할 수 있다.

  1. 각 간선을 확인하면서 두 노드의 루트노드를 확인한다.
    1.1 루트 노드가 서로 다르면 -> union 연산 수행
    1.2 루트 노드가 서로 같으면 cycle 발생
  2. 모든 간선에 대해 1 반복

소스코드로 나타내면 아래와 같다

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)
profile
Hongik CE

5개의 댓글

comment-user-thumbnail
2021년 5월 12일

잘 봤습니다~

1개의 답글
comment-user-thumbnail
2022년 3월 17일

좋은 글 감사드립니다. 다름이 아니라 질문이 하나 있어서 댓글 남깁니다:) find_parent 경로 압축에서 부모 테이블을 바꾸기 위해서는 parent[x]=find(parent,parent[x])부분이 있고, 그래프 union연산 순서가 오름차순(parent가 먼저 union을 거치도록)으로 되어 있거나 union 연산들을 진행 후에 parent[parent[x]]와 parent[x]가 다른 값이 있으면 업데이트해주는 과정을 필요로 하는 것이 아닌지 여쭈어보고 싶습니다.
추가적으로 parent 리스트가 함수 밖에서 정의되어 있는데 input parameter로 계속 넣어주어야 할 필요성이 있을지 여쭈어보고 싶습니다.
감사합니다.

답글 달기
comment-user-thumbnail
2023년 8월 18일

e.g 4개의 union 연산 union 1,4 union 2,3 union 2,4 union 5,6 는
union 2,4 가 union 1,2 여야 할 것 같아요

답글 달기
comment-user-thumbnail
2023년 9월 5일

감사합니다. 혹시 유니온 알고리즘은 양방향일때 적용되죠? 단방향에 적용하려니까 말이안맞는것 같고 머리가 터질꺼같네여ㅜㅜ

답글 달기