[java] 유니온 파인드(Union-Find)

이 글은 Do it! 알고리즘 코딩 테스트 - 자바편을 개인적으로 공부하고 정리하는 글임을 알립니다.

---

유니온 파인드

유니온 파인드는 여러 개의 원소들이 어떤 그룹(집합)에 속해 있는지를 빠르게 확인하고, 서로 다른 그룹을 하나로 합치기 위해 사용하는 자료구조이다.

예를 들어 친구 관계, 네트워크 연결, 그래프의 사이클 여부처럼 ‘서로 연결되어 있는지 아닌지’를 효율적으로 판별해야 하는 문제에서 매우 빠른 속도로 연산할 수 있기 때문에 자주 사용된다.

 

유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해있는지를 확인하는 find 연산으로 구성되어있는 알고리즘이다.

 

• union 연산 : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산
• find 연산 : 두 노드가 같은 집합에 속해 있는지를 확인하는 연산

 

처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화 한다.

 

 

2개의 노드를 선택해 각각 대표 노드를 찾아 연결하는 union 연산을 수행한다. 이때 노드 번호가 작은 쪽이 부모가 되도록 한다.

배열을 보면 1, 4와 5, 6을 union 연산으로 연결한다. 배열[4]는 1로, 배열[6]은 5로 업데이트한다.

 

4의 대표 노드에 1에 6의 대표 노드 5를 연결한다. -> union(1, 5)

이후 union(4, 6)으로 4와 6을 연결한다.

여기서 4, 6은 대표노드가 아니다. 그래서 각 노드의 대표 노드를 찾아 올라간 다음 그 대표 노드를 연결한다.

 

 

find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다.

find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킨다.

1. 대상 노드 배열에 index값과 value값이 동일한지 확인한다.
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index값과 value값이 같을 때까지 1~2를 반복한다. 반복이므로 이 부분은 재귀 함수로 구현한다.
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경한다.

 

경로 압축
find 연산은 시간 복잡도가 줄어드는 효과를 얻게 된다.
연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되는 것을 알 수 있다.
이렇게 되면 추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다.

한 번의 find 연산을 이용해 모든 노드가 루트 노드에 직접 연결되는 형태로 변경되는 것을 볼 수 있다.
이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다.

경로 압축은 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.

 

 

구현

public class UnionFind {
    static int[] parent;

    public static void main(String[] args) {
        init(5);

        union(1, 2);
        union(3, 4);

        System.out.println(isConnected(1, 2)); // true
        System.out.println(isConnected(2, 3)); // false

        union(2, 3);
        System.out.println(isConnected(1, 4)); // true
    }

    static void init(int n) {
        parent = new int[n + 1];
        for (int i = 1; i < n + 1; i++) parent[i] = i;
    }

    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return;

        // 항상 더 작은 노드를 부모로 삼는다
        if (rootX < rootY) parent[rootY] = rootX;
        else parent[rootX] = rootY;
    }

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // 경로 압축
    }

    static boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}