[알고리즘] 유니온 파인드 (Union - Find)

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 즉 {1, 2}와 {3, 4}는 서로소 집합이지만 {1, 2}와 {2, 4}는 서로소 집합이 아니다. 이러한 서로소 집합을 구할 때 유니온 파인드 알고리즘을 사용할 수 있다. 유니온 파인드의 개념을 알아보고 코드를 통해 구현해보자. 또한 유니온 파인드 알고리즘을 활용한 또 다른 알고리즘을 소개한다.

---

개념

유니온 파인드 알고리즘은 서로소 집합을 찾기위해 사용되는 알고리즘이다. 유니온 파인드는 Find과 Union라고 불리는 두 가지 연산으로 이루어져 있다.

• Find: 원소 x가 어느 집합에 포함되어 있는지 찾는다.
• Union: 원소 x가 포함된 집합과 원소 y가 포함된 집합을 합친다.

 

위의 연산을 통해 그래프 내에서 부분집합을 쉽게 구할 수 있다. 이제 python으로 구현하면서 조금 더 자세히 알아보자.

 

구현

유니온 파인드는 python에서 리스트를 통해 쉽게 구현할 수 있다. 

• N개의 원소를 갖는 리스트를 선언했다고 가정해보자.
• 리스트의 index는 노드의 번호가 되며 value는 부모 노드의 번호가 된다.
• 초기에 각 원소들은 자기 자신을 가리키도록 설정한다. 

N = 10
parent = [n for n in range(N)]

• 먼저 find 연산을 구현해보자.
• find 연산은 특정 노드가 속한 집합의 루트 노드를 반환하는 연산이다.
• 루트 노드를 찾기위해 재귀호출을 활용한다.

def find(n):
    # 노드 n의 부모 노드가 n일 때는 그대로 n을 반환
    if parent[n] == n:
        return n
    else:
        # n의 부모 노드가 자기 자신이 아닐 때는
        # 현재 자신의 부모 노드의 부모 노드를 찾는다.
        # 이를 통해 루트 노드를 구할 수 있다.
        m = find(parent[n])
        parent[n] = m
        return m

• 이제 노드 1이 속한 집합을 노드 0이 속한 집합으로 합쳐보자.
• 이를 위해 union 연산을 활용할 수 있다.
• 두 개의 노드를 입력받은 후에 각 노드의 부모 노드를 찾는다.
• 부모 노드가 다를 때 한 쪽 노드의 부모 노드를 다른 쪽의 노드로 설정한다.

def union(a, b):
    # 노드 a, b의 부모노드를 찾는다.
    a = find(a)
    b = find(b)
    # 두 노드의 부모노드가 다를 때 b노드의 부모 노드를 a로 설정한다.
    if a != b:
        parent[b] = a

# 노드 1이 속한 집합을 노드 0이 속한 집합으로 합친다.
union(0, 1)

# 이후 노드 1의 부모 노드를 출력하면 0이 출력된다.
print(find(1))

---

정리

• 서로소 집합을 만들기 위해 유니온 파인드를 활용할 수 있다.
• 유니온 파인드는 노드의 부모를 찾는 Find와 두 개의 노드들이 속한 집합을 합치는 Union으로 구성되어 있다.
• 유니온 파인드를 통해 최소 비용신장 트리를 구하는 알고리즘인 크루스칼 알고리즘을 구현할 수 있다.