TIL : Union-Find 알고리즘, Disjoint Set 자료구조 (6)

📚 자료구조

 ✔️ Disjoint Set이란?

 여집합이 없는 부분집합을 저장하고 조작하는 자료 구조. 한 마디로, 서로소 집합 자료구조

 세 가지 연산을 가진다. 

• 초기화, make-set(x) : x를 유일한 원소로 하는 새로운 set을 만든다. 
• 합치기, union(x, y) : x가 속한 set과 y가 속한 set을 합친다.
• 찾기, find(x) : x가 속한 set의 루트 노드 값을 리턴한다.

💡 특징

 부모 노드가 자식 노드를 가리키는 트리 구조와 다르게 분리 집합은 자식 노드가 부모 노드를 가리킨다.

💻 알고리즘

 ✔️ Union-Find 알고리즘이란?

 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.

 다시 말하면, disjoint set을 표현할 때 사용하는 알고리즘이다.

 

💡 특징

 분리 집합의 특징 때문에 가리키고 있는 노드의 정보를 저장하는 공간이 필요하다. (parent 리스트)

 ✔️ Find 연산

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

 단순하게 루트 노드가 누구인지 찾아주는 것뿐만 아니라,

 이미 구현된 부모 리스트의 값을 변경해서 낮은 레벨의 트리 구조로 계속 변경해준다.

 ✔️ Union 연산

def union(x, y):
    x = find(x)
    y = find(y)
    
    parent[y] = x

 Find 연산에서 트리의 레벨을 변경해주기 때문에 굳이 어떤 트리가 더 큰지 등의 추가적인 것을 따질 필요가 없다.