알고리즘(Java) - 유니온 파인드를 알아보자.

아래 모든 내용은 “프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 저, 인사이트” 책을 바탕으로 공부하여 정리하였습니다.

요약

유니온 파인드가 할 수 있는 일은 대부분 다른 그래프 알고리즘이나 자료 구조로도 할 수 있다. 하지만 구현이 매우 간단하고 동작 속도가 아주 빠르기 때문에 가능한 경우 유니온 파인드를 사용하는 것이 좋다. 유니온 파인드는 보통 그래프의 연결성 확인이나 가장 큰 집합을 확인할 때 활용한다.

상호 배타적 집합의 표현

그래프에서 A와 B는 연결되어 있는지 아닌지는 어떻게 확인할까? 그래프 내에서 연결된 원소들을 하나의 그룹으로 모아 1번 그룹, 2번 그룹으로 이름을 짓고 A와 B가 동일한 그룹인지 확인하는 방법으로 찾을 수 있을 것이다.

이 때 유용하게 사용할 수 있는 자료 구조가 트리이다. 위의 예시에서 원소는 오직 하나의 그룹에만 속한다고 할 때 각각의 그룹에서 대표자를 뽑는다. 이 때 A와 B가 속해있는 그룹의 대표자가 서로 동일하다면 A와 B는 동일한 그룹이라고 볼 수 있다. 이 예시에서 트리는 하나의 그룹으로 볼 수 있고 루트 노드라는 대표자가 존재한다. 따라서 모든 노드가 자신의 루트 노드가 누군지만 알고 있으면 루트 노드를 비교해서 동일한 그룹인지 파악할 수 있다.

이렇게 트리로 표현하면 두 집합을 하나의 집합으로 연결하기도 편리하다. 한 트리의 루트 노드를 다른 트리의 루트 노드 아래로 종속시키는 방법으로 할 수 있다.

이처럼 상호 배타적 집합을 트리로 표현하면 루트 노드를 찾는 찾기 연산, 두 상호 배타적 집합을 하나로 합치는 병합 연산 두 가지를 구현할 수 있다.

찾기 연산

루트 노드의 부모는 자기 자신이 된다. 따라서 시작점에서 자신과 부모 노드가 동일할 때까지 계속 부모 노드를 거슬러 올라가면 된다. 아래 그림에서 2번 노드의 부모는 1번, 1번 노드의 부모는 1번이므로 2번의 루트 노드는 1번으로 찾을 수 있다.

병합 연산

A가 속한 트리와 B가 속한 트리를 합친다고 하자. 가장 먼저 A의 루트 노드를 찾고 B의 루트 노드를 찾는다. 이 때 두 번의 찾기 연산을 수행한다. 이후 두 루트 노드 중 하나의 부모를 다른 루트 노드로 설정하면 병합이 이루어진다.

아래 그림은 4번 루트 노드를 1번 루트 노드 밑으로 종속시켜 하나의 트리로 만든 모습이다.

구현하기

단순 구현

이 트리를 1차원 배열로 구현할 수 있다. 찾기 연산과 병합 연산에서 부모 노드에서 자식 노드로의 접근은 필요하지 않다. 따라서 1차원 배열에서 각자 부모 노드만을 저장하면 트리를 단순하게 구현할 수 있다.

public class UnionFind {
    int[] parent;
    public UnionFind(int n) {
        parent = new int[n];
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int n) {
        if (n == parent[n]) return n;
        return find(parent[n]);
    }
    
    void merge(int a, int b) {
        a = find(a);    b = find(b);
        if (a == b) return;
        parent[a] = b;
    }
}

최초로 생성할 때 모든 노드는 서로 연결되어 있지 않으므로 각자 노드의 부모 노드는 자기 자신이다. 따라서 본인의 부모 노드를 자기 자신으로 초기화한다. 찾기 연산과 병합 연산은 기존의 개념 설명의 단순 구현이라고 보면 된다.

생성자의 시간 복잡도

모든 노드의 루트 노드를 자기 자신으로 초기화하므로 O(N)이 된다.

찾기 연산 시간 복잡도

최악의 상황을 가정하자. 만약 0과 1을 합치고 이후 1과 2를 합치고, 2와 3을 합치는 식으로 n-1번 노드까지 합친다고 하자. 그러면 트리가 연결 리스트와 동일한 구조를 가지게 된다. n-1번에서 0번까지 거슬러 올라가면 모든 노드를 탐색하므로 O(N)이 된다.

병합 연산 복잡도

두 번의 찾기 연산을 수행하므로 O(N)이 된다.

트리의 불균형 문제 해결한 구현

이처럼 한쪽으로 기울어지는 문제를 막기 위해 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리에 종속시켜야 한다는 제약 사항을 추가한다. 높이가 2와 3인 두 트리 treeA, treeB가 있다고 하자. treeB가 treeA에 종속되면 treeB의 루트 노드는 treeA의 루트 노드 아래에 가게 된다. 따라서 전체 높이는 treeB의 높이에서 한 단계 증가한 4가 된다.

반대로 treeA가 treeB에 종속되면 treeA의 루트 노드가 treeB의 루트 노드 아래에 가게 된다. treeA의 높이에서 한 단계 증가해도 기존 treeB의 높이와 동일하므로 여전히 3이 된다. 이처럼 높이가 낮은 트리를 높은 트리 아래에 종속시키면 불필요하게 높이가 증가하는 문제를 막을 수 있다.

따라서 이 제약 사항을 추가하면 높이가 동일한 두 트리를 병합할 때만 높이가 증가한다.

public class UnionFind {
    int[] parent;
    int[] rank;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    int find(int n) {
        if (n == parent[n]) return n;
        return find(parent[n]);
    }

    void merge(int a, int b) {
        a = find(a);    b = find(b);
        if (a == b) return;
        if (rank[a] > rank[b]) {
            //swap
            int temp = a;
            a = b;
            b = temp;
        }
        parent[a] = b; //항상 랭크(높이)가 작은 트리가 큰 트리에 종속되도록
        if (rank[a] == rank[b]) ++rank[b]; //트리의 높이가 동일할 때 합하면 높이 증가
    }
}

생성자의 시간 복잡도

모든 노드의 루트 노드를 자기 자신으로 초기화하므로 O(N)이 된다.

찾기 연산 시간 복잡도

불균형이 해소되어 트리의 높이가 h-1에서 h로 증가하기 위해서는 h-1 높이의 트리 두 개가 합쳐져야 한다. h-1 높이의 트리를 만들기 위해 최소 x개 필요하다면 h 높이의 트리는 최소 2x개 필요하다. 이를 통해 노드의 수(x)와 트리의 높이(h)의 관계는 로그 함수로 표현할 수 있음을 알 수 있다.

이 때 찾기 연산의 시간 복잡도는 트리의 높이와 비례하므로 시간 복잡도는 O(log N)이 된다.

병합 연산 시간 복잡도

두 번의 찾기 연산을 수행하므로 O(log N)이 된다.

경로 최적화 수행하기

이러한 찾기 연산을 최대한 줄일려면 트리의 높이를 최대한 작게 유지해야 한다. 아래와 같이 경로 최적화 이전 트리에서 6의 찾기 연산을 한번 한다고 하자. 찾기 연산으로 6의 부모가 0임을 이미 찾았다면 다시 6의 찾기 연산을 할 때 굳이 5 -> 2 -> 1을 거슬러 올라갈 필요가 있을까? 여기에서 중복이 발생하게 되고 이 중복을 줄임으로써 더 최적화를 할 수 있다. 6의 부모를 0으로 바꿔버리면 다음에 다시 6의 루트 노드를 찾을 때는 부모를 한 단계만 거슬러 올라가면 된다.

찾기 연산만 아래의 코드로 수정하면 재귀 함수 호출 과정에서 6의 부모 노드만 바뀌는 것이 아니라 6의 모든 조상들의 부모 노드가 루트 노드로 바뀌게 된다.

    int find(int n) {
        if (n == parent[n]) return n;
        return parent[n] = find(parent[n]);
    }

경로 최적화 이전

n	0	1	2	3	4	5	6	7
parent[n]	0	0	1	1	1	2	5	5

경로 최적화 이후

n	0	1	2	3	4	5	6	7
parent[n]	0	0	0	1	1	0	0	5

생성자의 시간 복잡도

모든 노드의 루트 노드를 자기 자신으로 초기화하므로 O(N)이 된다.

찾기 연산의 시간 복잡도

이 찾기 연산은 호출할 때마다 수행 시간이 바뀌기 때문에 추론하기 아주 어렵다. 알려진 바에 의하면 찾기 연산의 평균 시간은 O(a(N))이다. a(N)은 Ackermann function으로 모든 우주의 원자 개수를 N으로 해도 5 이하의 값이 나온다. 따라서 현실적인 모든 입력에 대해 상수 시간 O(1)에 동작한다고 보면 된다.

병합 연산의 시간 복잡도

두 번의 찾기 연산을 수행하므로 O(1)이다.

결론

최적화하지 않은 유니온 파인드 연산은 찾기, 병합 시 시간 복잡도는 O(N)이다. 하지만 약간의 최적화 코드를 추가하면 상수 시간에 동작한다. 따라서 일반적인 그래프 탐색 알고리즘에 비해 아주아주 빠른 시간에 동작하므로 유니온 파인드 연산을 활용할 수 있다면 활용하는 것이 좋은 선택이다. 유니온 파인드는 일반적으로 그래프의 연결성, 가장 큰 집합을 찾을 때 사용한다. 또한 크루스칼 알고리즘과 같이 다른 알고리즘의 일부로 사용되는 경우가 많다.

또한 유니온 파인드는 동적으로 변하는 그래프에 대응하기 좋다는 장점이 있다. 일반적인 그래프 탐색은 새로운 노드들이 추가되면 최적화 코드를 추가하지 않는 이상 다시 그래프 탐색을 수행해야 한다. 하지만 유니온 파인드는 병합 연산을 이미 구현하고 있으므로 새로운 노드들이 추가될 때 기존의 병합 연산을 활용할 수 있다.

다만 유니온 파인드 알고리즘으로 경로 찾기와 같은 그래프의 연결성 그 이상의 작업은 불가능하므로 이 경우는 그래프 탐색 알고리즘을 활용하는 것이 좋다.

algorithm	constructor	union	find
union-find	N	N	N
불균형 해소 union-find	N	log N	log N
경로 최적화 union-find	N	거의 1	거의 1

알고리즘 문제 풀이시

1. 코드 작성 전 단순히 그래프의 연결성, 가장 큰 집합을 찾는 문제인지 확인한다.
2. 이 주제에서 벗어나지 않는다면 유니온 파인드를, 벗어난다면 그래프 탐색을 고려한다.

연관 문제

1. 백준 1043 거짓말
2. 백준 1717 집합의 표현
3. 백준 4195 친구 네트워크
4. 알고스팟 에디터 전쟁

Reference

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 저, 인사이트