개념

서로소 집합 자료구조, Disjoint Set, Union-Find 등의 이름으로 불린다.
서로소는 공통으로 포함하는 원소가 없는 두 집합의 관계다.
즉, Disjoint Set은 공통되는 원소를 처리하기 위한 자료구조라 할 수 있다.
Disjoint Set은 Union, Find라는 두가지 연산을 가진다.
- Union : 원소를 하나의 집합으로 합친다.
- Find : 원소가 속한 집합이 어떤 집합인지 찾는다.

동작과정

조건

원소의 갯수가 1~6이 있고 아래와 같이 원소를 합친다.
처리할 연산 → (1, 2), (2, 3), (3, 4), (5, 6)

구현

원소의 갯수만큼 배열을 만들고 해당 배열은 자기 자신을 가리키는 각각의 집합으로 초기화한다.

union 메서드

public void union(int[] nodes, int a, int b) {
    a = find(nodes, a);
    b = find(nodes, b);

    if (a > b) nodes[a] = b;
    else nodes[b] = a;
}

root값을 최소값으로 정의하고, 큰 원소(부모노드)의 값이 작은 원소(자식노드)를 갖도록 한다.
- 2, 3을 예로 드는 경우 원소 3은 원소 2를 부모로 참조한다.
- 핵심은 서로소인지 판별하는 것이기 때문에 꼭 i번처럼 더 큰 값이 작은 값을 참조할 필요는 없지만, 직관적으로 보기 좋기 때문에 root값을 최소값으로 설정한다.
- 더 작은 값이 루트 노드가 되도록 if문을 작성

find 메서드

public int find(int[] nodes, int node) {
    if (nodes[node] != node) nodes[node] = find(nodes, nodes[node]);

    return nodes[node];
}

find 메서드는 재귀함수를 사용하여 해당 원소의 루트노드를 찾는다.
union메서드를 사용하여 합친 노드들은 각 부모노드를 참조하고 있어, 부모노드를 계속해서 타고 올라가서 확인해야 한다. 따라서 루트노드를 찾을 때마다 재귀로 거슬러 올라가기 때문에 O(N)의 시간복잡도를 가지게 된다.
최초에 find 메서드 호출시 해당 루트노드의 값을 저장하여 이후의 호출부턴 루트노드 값을 반환하도록 하게 되면, O(1)의 시간 복잡도로 줄일 수 있다.
- 루트 노드까지 찾고, 해당 값을 리턴해서 루트 노드의 값을 각 노드가 가질 수 있도록 저장한다.

코드

package datastructure;

public class DisjointSet {
    public void union(int[] nodes, int a, int b) {
        a = find(nodes, a);
        b = find(nodes, b);

        if (a > b) nodes[a] = b;
        else nodes[b] = a;
    }

    public int find(int[] nodes, int node) {
        if (nodes[node] != node) nodes[node] = find(nodes, nodes[node]);

        return nodes[node];
    }

    public boolean find(int[] nodes, int a, int b) {
        a = find(nodes, a);
        b = find(nodes, b);
        return a == b;
    }

    public static void main(String[] args) {
        int[] nodes = new int[7];

        for (int i = 1; i <= 6; i++)
            nodes[i] = i;

        DisjointSet ds = new DisjointSet();

        ds.union(nodes, 1, 2);
        ds.union(nodes, 2, 3);
        ds.union(nodes, 3, 4);
        ds.union(nodes, 5, 6);
        System.out.println("node 6의 부모 원소 : " + ds.find(nodes, 6));
        System.out.printf("%s와 %s는 같은 부모 원소를 가졌는가? : \\n", 3, 4);
        System.out.println(ds.find(nodes, 3, 4));
    }
}