[자료구조] 분리집합(Disjoint set) 개념 및 JAVA 구현

Disjoint set?

Disjoint set은 서로 중복되지 않는 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.
교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰때 유용하게 쓰인다.

분리집합은 자식 노드가 부모 노드를 가리키는 형태이다. 또한 교집합입 없는 집합이기 때문에 차집합 연산이 있지 않다.

오직 Union-Find알고리즘을 사용하며 배열, 연결리스트, 비트벡터 등으로 이용하여 구현할수 있지만 구조는 트리구조를 가지게 된다.

Union 연산

두개의 집합을 합한다. 각 집합의 부모 값을 얻어와 한쪽 부모가 다른쪽 부모를 가르키게 해 한개의 부모만 있는 집합을 만든다. 결국 한개의 집합에는 하나의 부모만을 가지게 된다.

//N은 원소들을 넣은 배열 
public void union(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        N[bp] = ap;
    }

Find 연산

원소가 속해있는 집합의 부모를 찾는 연산이다. A와 B의 각각의 부모를 구했을때 같은 부모를 가르키면 같은 집합, 서로 다르면 다른집합에 속해있다고 판단한다.
여기서 연산속도를 높이기 위해 자식노드는 항상 부모를 가리키고 있어야 연산속도가 빠르다. 그러므로 Find연산을 할 때마다 부모의 값을 넣어주는 연산을 해줘야 한다.

public static int findParent(int x) {
        if(x == N[x])
            return N[x];
        else
            return N[x]=findParent(N[x]);//부모를 찾을 때마다 최상위 부모로 항상 업데이트 해줘야함
    }

Find연산은 모든 Union 연산을 할때마다 불려지게 된다. 그 이유는 부모를 찾으면서 원소들의 부모 값을 집합의 부모로 업데이트 해줘야 같은 집합에 속해있는지 아닌지 판단할때 빠르게 판단할 수 있게 된다.

---

분리 집합 문제

https://www.acmicpc.net/problem/1717

내가 푼 해답

https://go-coding.tistory.com/27

[백준 1717번] 집합의 표현