(알고리즘) Disjoint Set (Union-Find)

Union-Find (Disjoint Set)이란?

 Union-Find, 또는 Disjoint Set 자료구조는 서로소 집합을 관리하는 자료구조(알고리즘)이다. 이 자료구조는 여러 개의 원소들이 각각의 집합에 속해 있을 때, 두 원소가 같은 집합에 속해 있는지 확인하거나, 두 집합을 하나로 합치는 작업을 빠르게 수행할 수 있다. 이 자료구조는 그래프에서 연결된 컴포넌트를 찾거나 사이클을 검출하는 데 자주 사용된다.

 

Union-Find 구현 방법

Union-Find는 두 가지 주요 연산으로 구성된다 이름 그대로 Union 연산과 Find 연산이 그것이다.

 

Union 연산

 Union 연산은 두 집합을 하나의 집합으로 합치는 연산이다. 두 원소의 루트를 찾아 하나의 루트로 통일하는 방식으로 진행된다. 이때 랭크(Rank)를 사용하여 항상 높이가 낮은 트리를 높은 트리 밑에 합쳐 트리의 높이를 줄인다.

 

 그림으로 설명하면 다음과 같다

 

초기 상태

[사진 3] 초기 상태, Union(1, 3)을 수행하기 전

 

 

Union (1, 3을 수행한 후)

[사진 4] Union(1, 3)을 수행한 후

 

 

Find 연산

Find 연산은 특정 원소가 속한 집합의 대표(루트)를 찾는 연산이다. 이때 경로 압축(Path Compression)을 사용하면, 원소의 부모를 루트로 직접 연결하여 나중에 Find 연산을 더 빠르게 할 수 있다.

 

그림으로 설명하면 다음과 같다

 

 

초기 상태

[사진 1] 초기 상태

 

 

Find 연산 수행 전

[사진 2] Find 연산 수행 전

 

 

Find 연산 수행 후

[사진 3] Find 연산 수행 후

 

 

 

Union-Find 구현

문제 설명

현수네 반 학생들의 친구 관계를 파악하는 문제이다. 학생들은 1부터 N까지 번호가 부여되어 있고, 각 두 명의 학생이 친구 관계인 번호 쌍이 주어진다. 예를 들어, (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구이며, 3번 학생과 4번 학생이 친구이다. 이를 통해 1번 학생과 4번 학생은 간접적으로 친구 관계가 된다. 주어진 숫자쌍을 통해 특정 두 학생이 친구인지 여부를 판별하는 프로그램을 작성하는 것이 목표이다.

 

전체 코드

public class UnionFindExample {

    static int[] parent = new int[10];

    public static void main(String[] args) {
        // 초기화: 각 학생이 자기 자신을 부모로 가리키도록 설정
        for(int i = 0; i < parent.length; ++i) {
            parent[i] = i;
        }

        // 친구 관계 설정 (Union 연산)
        union(1, 2);
        union(2, 3);
        union(3, 4);
        union(1, 5);
        union(6, 7);
        union(7, 8);
        union(8, 9);

        // 특정 두 학생이 친구인지 확인 (Find 연산)
        if (find(3) == find(8)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    // Union 연산: 두 집합을 하나로 합침
    public static void union(int target, int source) {
        int targetRoot = find(target);
        int sourceRoot = find(source);

        if (targetRoot != sourceRoot) {
            parent[targetRoot] = sourceRoot;
        }
    }

    // Find 연산: 특정 원소가 속한 집합의 루트를 찾음
    public static int find(int target) {
        if (parent[target] == target) {
            return target;
        } else {
            parent[target] = find(parent[target]);  // 경로 압축
            return parent[target];
        }
    }
}

 

각 단계별 로직 설명

초기화

각 학생이 자기 자신을 부모로 가리키도록 parent 배열을 초기화한다.

for(int i = 0; i < parent.length; ++i) {
    parent[i] = i;
}

 

초기 상태

[사진 5] 초기 상태

 

Union 연산 수행

union(1, 2): 1번과 2번 학생을 같은 집합으로 합침

[사진 6] union(1, 2) 연산 수행 결과

 

 

union(2, 3): 2번과 3번 학생을 같은 집합으로 합침

[사진 7] union(2, 3) 연산 수행 결과

 

union(3, 4): 3번과 4번 학생을 같은 집합으로 합침

[사진 8] union(3, 4) 연산 수행 결과

 

union(1, 5): 1번과 5번 학생을 같은 집합으로 합침

[사진 9] union(1, 5) 연산 수행 결과

 

 

사진 9의 연산 수행 결과를 자칫 [0, 5, 3, 4, 4, 5, 6, 7, 8, 9]라고 착각할 수 있다.
union[target, source] 연산의 결과를 단순히 target의 값을 source로 바꾼다. 라고 오해할 수 있는 것이다.

union 연산자는 집합체를 이루기 위해서 "각 노드의 루트를 찾아 두 집합을 합치는 과정" 임을 잊지말자

 

 

union(6, 7): 6번과 7번 학생을 같은 집합으로 합침

[사진 10] union(6, 7) 연산 수행 결과

 

union(7, 8): 7번과 8번 학생을 같은 집합으로 합침

[사진 10] union(7, 8) 연산 수행 결과

 

 

union(8, 9): 8번과 9번 학생을 같은 집합으로 합침

[사진 11] union(8, 9) 연산 수행 결과

 

따라서 이러한 형태의 집합 군이 형성됨을 알 수 있다.

[사진 12] union 과정을 거듭한 결과 집합 군들이 크게 두 가지로 나누어짐을 알 수 있다. (0번은 논외)

 

Find 연산 수행

find(3)와 find(8)을 수행하여 두 학생이 같은 집합에 속하는지 확인한다.

 

경로 압축을 수행하면 3번 사람의 루트 값을 찾아 find(3)을 수행한 결과 5가 반환되고

경로 압축을 수행하면 8번 사람의 루트 값을 찾아 find(8)을 수행한 결과 9가 반환됨을 알 수 있다.

 

두 루트가 다르므로 3번 학생과 8번 학생은 친구가 아니다.