서로소 집합 (Disjoint Sets)

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

 

예를 들어, {1, 2}와 {3, 4}는 서로소 집합이다. 반면에 {1, 2}와 {2, 3}은 2라는 원소가 공통적으로 포함되기 때문에 서로소 관계가 아니다.

 

서로소 집합 자료구조를 다루기 위해 union과 find 2개의 연산을 이용한다. 따라서 union-find 자료구조라고 불리기도 한다.

 

서로소 집합 자료구조

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1. A와 B의 루트 노드 A', B'를 각각 찾는다.
   2. A'를 B'의 부모 노드로 설정한다.
2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

위 알고리즘을 예시를 통해 알아보자.

전체 집합 {1, 2, 3, 4, 5, 6}이 6개 원소로 구성되어 있을 때, 아래와 같은 4개의 union 연산이 주어져 있다.

• union 1, 4
• union 2, 3
• union 2, 4
• union 5, 6

이를 트리구조로 나타내면 아래와 같다.

 

Step 0)

모든 원소가 자기 자신을 부모로 가지도록 초기화 한다.

노드번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

 

 

Step 1) union 1, 4

노드 1과 노드 4의 루트 노드를 찾는다. 현재 루트 노드는 각각 1과 4이기 때문에 더 작은 노드를 큰 노드의 부모로 설정한다.

노드번호	1	2	3	4	5	6
부모	1	2	3	1	5	6

 

 

Step 2) union 2, 3

2와 3을 합친다. 마찬가지로 더 작은 노드 2를 3의 부모로 설정한다.

노드번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

 

 

Step 3) union 2, 4

2와 4를 합친다. 노드 2와 노드 4의 루트 노드를 찾아서 설정하면 된다. 현재 루트 노드는 각각 2와 1이기 때문에, 더 작은 노드인 1을 2의 부모로 설정한다.

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	6

 

 

Step 4) union 5, 6

위와 동일하게 루트 노드를 찾아 부모 설정을 한다.

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	5

---

서로소 집합 코드

public class Chap10_union_find {
    static int find_parent(int[] parent, int x) {
        // 루트 노드에 도달할때 까지 재귀 호출
        if(parent[x] != x)
            parent[x] = find_parent(parent, parent[x]);
        return parent[x];
    }

    // 합집합
    static void union_parent(int[] parent, int a, int b) {
        a = find_parent(parent, a);
        b = find_parent(parent, b);
        if(a < b)
            parent[b] = a;
        else
            parent[a] = b;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());   // 노드 개수 입력
        int e = Integer.parseInt(st.nextToken());   // 간선 개수 입력

        // 부모 배열 초기화 (초기 상태 : 자기 자신)
        int[] parent = new int[v+1];
        for(int i=1; i<=v; i++)
            parent[i] = i;

        // union 연산 수행
        for(int i=0; i<e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            union_parent(parent, a, b);
        }

        // 각 원소 집합 출력
        System.out.print("각 원소가 속한 집합: ");
        for(int i=1; i<=v; i++) {
            System.out.print(find_parent(parent, i) + " ");
        }
        System.out.println();

        // 부모 테이블 출력
        System.out.print("부모 테이블: ");
        for(int i=1; i<=v; i++) {
            System.out.print(parent[i] + " ");
        }
    }
}

---

서로소 집합 알고리즘 응용

사이클 판별

무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.

 

간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하면 사이클을 판별할 수 있다.

 

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
   1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
   2. 루트 노드가 서로 같다면 사이클이 발생한 것
2. 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복

// 응용 - 사이클 판별
boolean cycle = false;

for(int i=0; i<e; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    if(find_parent(parent, a) == find_parent(parent, b)) {
        cycle = true;
        break;
    }
    else {
        union_parent(parent, a, b);
    }
}
if(cycle)
    System.out.println("사이클 발생");
else
    System.out.println("사이클 발생 X");