[Algorithm] 유니온 파인드

Algorithm in HelloMinchan

[Algorithm] 유니온 파인드

(글쓴날 : 2020.05.16)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

---

 

 

유니온 파인드

---

1) 유니온 파인드란?

유니온 파인드란 집합을 관리하는 트리 형태의 자료구조로 Disjoint-set(서로소 집합, 분리 집합)이라고도 하며, 보통 배열에서 인덱스를 노드로 나타내어 각 인덱스의 값에 해당 인덱스의 부모 노드를 저장합니다.

유니온 파인드는 주로 그래프 문제에 적용할 수 있으며, 다른 그래프 알고리즘인 Dijkstra algorithm, Bellman-Ford algorithm 등과 달리, 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용됩니다.

 

핵심 연산으로는 2가지가 있으며, 유니온 파인드라는 이름과 걸맞게 다음과 같습니다.

1) union (서로 다른 두 트리(집합)를 합치는 연산)

2) find (루트 노드를 찾는 연산)

 

먼저, find 연산입니다.

find 연산은 어떤 노드를 인자로 넘겼을 때, 해당 노드의 루트 노드를 반환하는 연산으로,

실 사용 예로는 임의의 두 노드가 연결되어 있는지(루트 노드가 같은지) 확인할 때 쓰이며, 보통 재귀 호출의 형태로 구현합니다.

또한, 시간 복잡도 효율을 높이기 위해 find 연산에서 경로 압축 최적화를 합니다.

(재귀 호출 시, 자식 노드들의 값을 모두 루트 노드로 바꾸어 Skewed Tree를 방지합니다.)

 

다음으로, union 연산입니다.

union 연산은 서로 다른 두 트리(집합)를 합치는 연산으로, 보통 각 트리의 루트 노드를 비교하여 둘 중 작은 루트 노드를 기준으로 합치게 됩니다.

따라서, union 연산을 하기 위해서는 사전에 반드시 find 연산이 필요하며 이는 코드상으로도 마찬가지입니다.

(union 연산 함수 이름 작성 시, C/C++의 경우 union이 공용체를 지정하는 키워드로 이미 존재하므로 보통 merge로 표현하는 것 같습니다.)

---

2) 코드

위에서 설명한 유니온 파인드의 핵심 연산인 union 연산과 find 연산을 함수화하여 실제 사용해 본 코드입니다.

 

* Python 코드

# find 연산
def find(target):
    if target == parent[target]:
        return target
 
    # 경로 압축 최적화
    parent[target] = find(parent[target])
    return parent[target]
 
# union 연산
def union(a, b):
    a = find(a)
    b = find(b)
 
    # 작은 루트 노드를 기준으로 합침
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
parent = [0, 1, 2, 3, 4, 5]
 
# 노드 3과 노드 5가 같은 집합인지 비교
# 출력 결과 : 다른 집합입니다!
if find(3) == find(5):
    print("같은 집합입니다!")
else:
    print("다른 집합입니다!")
 
# 노드 3과 노드 5를 union 연산(합침)
union(3, 5)
 
# 노드 3과 노드 5가 같은 집합인지 비교
# 출력 결과 : 같은 집합입니다!
if find(3) == find(5):
    print("같은 집합입니다!")
else:
    print("다른 집합입니다!")

---