[알고리즘] disjoint-set(union find) 알고리즘

1. union find(disjoin-set)란?

• 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 다수의 노드들 중에 연결된 노드를 찾거나, 노드들을 합칠 때 사용하는 알고리즘

1~10까지 있다고 가정할 때, 아래와 같은 연결 구조를 가지고 있다고 가정하자.

첫째 줄 : 원소의 번호, 둘째 줄 : 원소의 관계

위 그림을 표현(각각의 부모노드 작성)

[ 진행과정 ]

• 1과 2가 연결되었으면, 원소 2의 정보를 1로 바꾼다.
• 1, 2, 3, 4가 모두 연결되어있어 같은 집단에 속하지만, 처음에는 각자의 부모노드를 작성한다.
• 3과 2는 연결되어있다. -> 3의 연결정보를 2로 바꾼다. -> 2와 1은 연결되어있다. -> 3과 1은 연결되어있으므로 3의 연결정보를 1로 바꾼다.

최종 표

 

---

구현

• 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화
• Union(합치기) : 두 원소 a, b가 주어질 때, 이들이 속한 두 집합을 하나로 합친다.
• Find(찾기) : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환