서로소 집합

---

서로소 집합

공통 원소가 없는 두 집합을 의미한다.

서로소 집합 자료구조(Disjoint Set Union, DSU)

서로소 집합들로 나누어진 원소들의 집합을 효율적으로 관리하기 위한 자료구조

해당 자료구조는 아래의 두 가지 연산으로 조작할 수 있다.

• 찾기(find)

  • 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
  • 다시 말해, 특정한 원소가 속한 집합의 루트 원소가 무엇인지 찾는 연산

• 합집합(union)

  • 찾기 연산으로 두 집합의 루트 원소를 찾아, 두 루트 원소 중 값이 더 작은 집합에 다른 집합을 합치는 연산

    예를 들어, A집합과 B집합의 루트 원소 중 A집합의 루트 원소가 더 작다면, B집합의 루트가 A집합의 루트에 연결된다.

정리

• 서로소 집합 자료구조는 각 서로소 집합(원소)을 트리 자료구조로 표현하며, 하나의 DSU는 여러 개의 트리로 구성된다.

기본 구현 예제

// 노드별 부모 노드 번호를 저장하는 배열
public static int[] parent = new int[100_001];

// 특정 원소가 속한 집합의 루트 노드를 찾기
public static int findParent(int x) {
    // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if (x == parent[x]) {
        return x;
    }
    return findParent(parent[x]);
}

// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

경로 압축 기법(Path Compression)

기존 구현에서는 parent 배열에 노드별 부모 노드 번호만 저장하고, findParent 메소드를 재귀적으로 호출하여 루트 노드를 찾아냈다.
그러나 DSU에서는 결국 루트 노드 번호를 통해 원소가 어떤 집합에 속하는지 확인하고 합치는 작업을 수행하므로, 최종적으로 중요한 정보는 “루트 노드 번호”이다.
따라서, find 연산 중에 경로상에 있는 모든 노드의 부모를 직접 루트 노드로 갱신함으로써 이후에 같은 노드를 찾을 때 깊이가 얕아지도록 하는 최적화 기법을 경로 압축이라고 부른다.

경로 압축 구현 예제

// 노드별 루트 노드 번호가 저장된 배열
public static int[] root = new int[100_001];

// 특정 원소가 속한 집합의 루트 노드를 찾기 (경로 압축 적용)
public static int findRoot(int x) {
    // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출하고
    // 이후에 x의 부모를 루트 노드로 바로 갱신한다.
    if (x == root[x]) {
        return x;
    }
    return root[x] = findRoot(root[x]);
}

// 두 원소가 속한 집합을 합치기
public static void union(int a, int b) {
    a = findRoot(a);
    b = findRoot(b);
    if (a < b) {
        root[b] = a;
    } else {
        root[a] = b;
    }
}

활용 예제

• 크루스칼 알고리즘(Kruskal’s Algorithm)

• 사이클 탐지(Cycle Detection)

  • 무방향 그래프에서 사이클 여부를 확인할 때 유용하다.
    각 간선의 두 정점을 확인하며, 이미 같은 집합에 속해 있다면 사이클이 존재한다고 판단한다.

서로소 집합을 이용한 사이클 판별 예제

아래는 무방향 그래프에서 간선 정보를 입력받아 DSU를 통해 사이클 존재 여부를 판별하는 예제이다.

import java.util.*;

public class CycleDetectionWithDSU {
    // 노드 최대 개수(예시): 100,000
    public static int MAX = 100_001;
    public static int[] parent = new int[MAX];

    // 초기화: 모든 노드를 자기 자신을 가리키도록 설정
    public static void initialize() {
        for (int i = 1; i < MAX; i++) {
            parent[i] = i;
        }
    }

    // 경로 압축 없이 단순히 루트 노드를 찾는 메소드
    public static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]); // 경로 압축 적용
    }

    // 두 집합을 합치는 메소드
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 노드 개수 n, 간선 개수 m 입력
        int n = sc.nextInt();
        int m = sc.nextInt();

        // DSU 초기화
        initialize();

        boolean cycleExists = false;

        // 간선 정보 입력
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            // 두 정점의 루트가 같다면 사이클 발생
            if (find(u) == find(v)) {
                cycleExists = true;
                // 사이클을 발견하더라도 모든 간선을 확인하려면 continue,
                // 즉시 종료하려면 break를 사용해도 된다.
            } else {
                // 아니면 두 집합을 합친다.
                union(u, v);
            }
        }

        if (cycleExists) {
            System.out.println("사이클이 존재합니다.");
        } else {
            System.out.println("사이클이 존재하지 않습니다.");
        }

        sc.close();
    }
}