서로소 집합(Disjoint Set)과 Union-Find 알고리즘

서로소 집합(Disjoint Set)

서로소 집합(상호배타 집합)은 서로 중복되어 포함된 원소가 없는 집합을 의미함. 다시 말해 교집합이 없는 집합!

따라서 집합에 속한 하나의 특정 원소를 통해 각 집합을 구별할 수 있고, 이 원소를 대표자(representative)라고 함.

서로소란?

수학에서의 서로소는 정수나 다항식 간 최대 공약수가 1인 관계를 말함

서로소 집합의 표현

연결 리스트
- 같은 집합 원소들을 연결 리스트로 관리
- 연결 리스트의 가장 앞에 위치한 원소를 대표자로 설정
- 각 원소는 집합의 대표 원소를 가리키는 링크를 가짐
트리
- 하나의 집합을 하나의 트리로 관리
- 자식 노드가 부모 노드를 가리키는 형태이고, 루트 노드가 대표자가 됨

서로소 집합의 연산

Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성
- 초기 세팅 개념으로, 모든 원소들이 자기 자신만을 원소로 하는 집합을 구성하면 서로소 집합들이 만들어짐
- 따라서 N개의 원소로 원소가 1개씩인 N개의 집합이 생성됨
Find-Set(x) : x를 포함하는 집합을 찾는 연산
- 대표자를 찾는 연산
- 자신이 곧 대표자일 수 있고, 아니라면 부모의 대표자를 재귀적으로 찾아가 자신의 대표자를 찾음
Union(x, y) : x와 y를 포함하는 두 집합을 결합하는 연산
- 대표자를 통한 결합!!!
- 대표자가 같아 같은 집합이면 연산하지 않고, 아니라면 y가 속했던 집합의 대표자를 x가 속한 집합의 대표자로 대치

기본 서로소 집합 연산의 문제점

서로소 집합은 서로가 같은 집합인지 확인하기 위해서 각 원소의 대표자인 루트노드까지 타고 올라가야 한다. 또한 두 집합을 결합할 때도 원소끼리 결합하는 것이 아니라 대표자끼리 결합하는 방식을 취하기때문에 이 때도 역시나 대표자를 찾기 위해 루트 노드까지 타고 올라가야 한다.

만약 find-set() 혹은 union()을 시도하는 원소들이 트리의 말단에 위치해있다면 루트 노드까지 탐색해 올라가는 과정에서 비용이 꽤나 소모될텐데 아깝지 않은가?!

서로소 집합에서의 트리는 부모 노드와 자식 노드 간 계층 관계를 표현하고 있지 않기때문에(단지 같은 집합에 속한 원소를 표현한 것 뿐) 이 계층 관계를 해지해도 된다. 따라서 연결 리스트를 이용한 구현이 훨씬 효율적이다.

하지만 세상은 넓고 트리 구조를 유지하면서도 연산을 효율적으로 할 수 있는 알고리즘도 존재한다.

연산 효율을 높인 서로소 연산

Union by Rank(rank를 이용한 union)

Union by Rank1

Union by Rank2

각 노드는 자신을 루트로 하는 서브 트리의 높이를 rank로 저장하고 있음
두 집합에 대해 union을 시도할 때, rank가 낮은 집합을 rank가 높은 집합에 결합함
최종적으로 하나가 된 집합의 rank는 rank가 높았던 집합의 rank이므로 rank의 변화가 생기지 않음
단, 결합하려는 두 집합의 rank가 동일하다면, rank가 1개는 늘어날 수밖에 없음

Java

class RankDisjointSet {
    int N;              // 전체 원소 개수
    int[] parents;      // 각 원소의 부모 인덱스 저장
    int[] ranks;        // 각 원소의 서브트리의 높이 저장

    // 초기 서로소 집합 생성
    public void makeSet() {
        parents = new int[N];
        ranks = new int[N];

        // 초기 서로소 집합은 자기 자신만을 포함한 집합이므로 대표자는 자기 자신을 가리킴
        for (int i=0; i<N; i++) parents[i] = i;
    }

    // 대표자 찾기
    public int findSet(int x) {
        if (parents[x] == x) return x;        // 대표자가 자기 자신이면 자신을 리턴
        return parents[x] = findSet(parents[x]);           // 아니면 자신의 부모의 대표자를 재귀적으로 찾아 자신이 속한 집합의 대표자를 찾음
    }

    // 두 원소가 속한 집합 결합
    public boolean union(int x, int y) {
        int xRoot = findSet(x);     // 원소 x가 속한 집합의 대표자
        int yRoot = findSet(y);     // 원소 y가 속한 집합의 대표자

        // 만약 두 집합의 대표자가 같으면, 즉 두 원소가 같은 집합에 포함될 경우 결합 실패
        if (xRoot == yRoot) return false;

        // rank 기준 결합
        if (ranks[xRoot] <= ranks[yRoot]) {      // rank가 더 큰 쪽으로 결합
            parents[xRoot] = yRoot;              // rank가 작은 쪽 부모를 rank가 큰 쪽 집합의 대표자로 설정
            
            if (ranks[xRoot] == ranks[yRoot]) ranks[yRoot]++;     // rank가 동일한 집합 결합 시 rank가 1개 늘어날 수밖에 없음
        } else parents[yRoot] = xRoot;

        return true;
    }
}

Path Compression(경로 압축)

Path Compression

Find-Set()을 통해 접근하게 되는 자신의 모든 부모 노드들이 직접 루트 노드를 가리키도록 pointer를 변경
결과적으로 각 원소의 부모 노드는 자신이 속한 집합의 대표자가 됨
대표자가 여러 원소들을 한꺼번에 물고있는 형태
path compression은 Find-Set() 연산을 수행할 때 이루어지므로 연산을 하지 않으면 path compression도 일어나지 않음

Java

class PathCompressDisjointSet {
    int N;              // 전체 원소 개수
    int[] parents;      // 각 원소의 부모 인덱스 저장

    // 초기 서로소 집합 생성
    public void makeSet() {
        parents = new int[N];

        // 초기 서로소 집합은 자기 자신만을 포함한 집합이므로 대표자는 자기 자신을 가리킴
        for (int i=0; i<N; i++) parents[i] = i;
    }

    // 대표자 찾기
    public int findSet(int x) {
        if (parents[x] == x) return x;               // 대표자가 자기 자신이면 자신을 리턴
        return parents[x] = findSet(parents[x]);     // 아니면 자신의 부모에게 바로 자신이 속한 집합의 대표자를 대치(path compression)
    }

    // 두 원소가 속한 집합 결합
    public boolean union(int x, int y) {
        int xRoot = findSet(x);     // 원소 x가 속한 집합의 대표자
        int yRoot = findSet(y);     // 원소 y가 속한 집합의 대표자

        // 만약 두 집합의 대표자가 같으면, 즉 두 원소가 같은 집합에 포함될 경우 결합 실패
        if (xRoot == yRoot) return false;

        parents[yRoot] = xRoot;     // 첫번째 매개변수로 들어온 원소가 속한 집합에 두번째 매개변수 집합 결합(무조건 대표자끼리 결합)
        return true;
    }
}

각 서로소 집합의 원소 개수 구하기

지금까지 구현한 서로소 집합은 parents 배열에 자신의 부모 인덱스를 저장해두어 대표자까지 찾아 올라가거나, 아니면 바로 대표자를 저장하여 루트 노드까지 찾아 올라가는 시간을 단축하기도 했다.

이번에는 parents 배열을 아주 조금 손 봐서 각 집합의 원소 개수를 구할 수 있도록 한다. 쉽게 말해 parents 배열에 부모 인덱스나 대표자를 저장하는 대신 집합의 원소 개수를 저장한다. 기본 원리는 다음과 같다.

최초 Make-Set() 연산 시 parents 배열에 집합의 대표자(최초에는 자기 자신이 대표자임) 인덱스를 저장하는 대신, 집합 원소 개수 * (-1)를 저장함
- 이때, parents 배열에는 무조건 집합 원소 개수를 저장하는 것이 아니라, 각 집합의 대표자인 경우에만 원소 개수를 저장. 나머지 원소들은 역시 부모 인덱스나 대표자 인덱스를 저장
- (-1)을 곱하는 이유 : 일반 원소들이 저장한 인덱스와 대표자 원소가 저장한 집합 원소 개수를 구분하기 위해 개수는 (-1)을 곱하여 음수 상태로 저장. 따라서 실제 집합 원소 개수를 구하기 위해서는 절댓값을 취하면 됨.
이후 union() 연산 시 두 원소가 속한 집합의 대표자를 참조하면 결국 두 집합 각각의 원소 개수를 구할 수 있고, 이를 기준으로 결합을 시도함. 집합 원소 개수가 적은 쪽에서 많은 쪽으로 결합
union() 연산 결과 집합의 원소가 더 많았던 대표자는 집합 원소 개수가 늘어나고, 집합 원소가 더 적었던 대표자는 자신의 대표자를 집합의 원소가 더 많았던 대표자로 대치함으로써 결합 표현

Java

class CountDisjointSet {
    int N;              // 전체 원소 개수
    int[] parents;      // 각 원소의 부모 인덱스 저장

    // 초기 서로소 집합 생성
    public void makeSet() {
        parents = new int[N];

        // 초기 서로소 집합 생성 시 대표자는 자기 자신이고 원소 개수도 자기 자신 하나뿐이므로 -1로 초기화
        for (int i=0; i<N; i++) parents[i] = -1;
    }

    // 대표자 찾기
    public int findSet(int x) {
        if (parents[x] < 0) return x;                // 대표자만이 원소 개수인 음수 값을 저장하고 있으므로 자기 자신이 대표자이면 자신을 반환
        return parents[x] = findSet(parents[x]);     // 아니면 자신의 부모에게 바로 자신이 속한 집합의 대표자를 대치(path compression)
    }

    // 두 원소가 속한 집합 결합
    public boolean union(int x, int y) {
        int xRoot = findSet(x);     // 원소 x가 속한 집합의 대표자
        int yRoot = findSet(y);     // 원소 y가 속한 집합의 대표자

        // 만약 두 집합의 대표자가 같으면, 즉 두 원소가 같은 집합에 포함될 경우 결합 실패
        if (xRoot == yRoot) return false;

        // 두 집합의 원소 개수를 비교하여 원소가 더 많은 쪽으로 결합
        if (parents[xRoot] < parents[yRoot]) {     // 원소 개수 많으면(음수가 커지면 개수를 의미하는 절댓값이 더 커짐)
            parents[xRoot] += parents[yRoot];      // 원소 개수 적은 쪽의 원소 개수를 원소 개수 많은 쪽으로 넘겨주고
            parents[yRoot] = xRoot;                // 원소 개수 적은 쪽의 대표자의 부모를 원소 개수 많은 쪽 대표자로 설정
        } else {
            parents[yRoot] += parents[xRoot];
            parents[xRoot] = yRoot;
        }
        return true;
    }
}