상호 배타적 집합 (Disjoint Set) / Union Find/ 파이썬

1. 상호 배타적 집합과 유니온 파인드

상호 배타적 집합이란 서로간의 교집합이 없는 부분집합을 의미한다.

이를 표현하기 위해 유니온 파인드(Union Find) 라는 자료구조를 사용한다.

 

상호 배타적 자료구조를 표현하기 위해선 크게 3가지 연산이 필요하다.

1. 초기화(Initialization) : n개의 원소를 n개의 집합에 포함되어 있도록 초기화

2. 합치기(Union) : 두 원소에 대해 이 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합친다.

3. 찾기(Find) : 임의의 원소가 어떤 집합에 속해 있는지 반환

 

=> 이러한 연산을 클래스로 구현해주면 된다.

 

2. 구현 

다음은 파이썬으로 구현한 Navie한 Union 파인드이다.

class NaiveDisjointSet():
    parent =[] #부모 리스트
    def __init__(self, n): #부모 리스트 초기화
        self.parent =[i for i in range(n)]

    def find(self, u): # 특정 원소 u가 어떤 집합에 포함되어 있는지 재귀적으로 반환(가장 상위 부모를 반환)
        if u == self.parent[u]: return u
        return self.find(self.parent[u])

    def merge(self,u,v): # 두 집합을 합쳐준다.
        u = self.find(u) #u의 가장 상위 부모를 찾는다.
        v= self.find(v)  #v의 가장 상위 부모를 찾는다.
        if (u==v): return # 이 둘이 같다면 종료
        self.parent[u] = v #아니라면 u의 부모를 변경

 

사실 알고리즘 문제에서는 이런 식으로 사용하는게 어려움으로 아래와 같이 사용하면된다.

"""
N : 노드의 개수
edges : 간선 정보가 포함되어 있는 리스트
edges[i] : (시작노드, 도착노드, 가중치)
"""

# parents[i] : i번째 노드의 부모
parents = [i for i in range(N)] 

def find(parents, u):
    """
	노드 u의 부모를 찾는 함수
    """
    if u != parents[u]:
        parents[u] = find(parents, u)
    return parents[u]
   
def union(parents, u, v):
    """
    노드 u와 노드 v를 합치는 함수
    """
    p_u = find(parents, u)
    p_v = find(parents, v)
    if p_u == p_v: return
    parents[u] = v