유니온 파인드(Union-Find) : 서로소 집합을 판단하기 위한 자료구조

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

서로소 집합 자료구조

서로 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

• 합집합 Union : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• 찾기 Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
  서로소 집합 자료구조는 Union-Find 자료구조라고 한다.

동작과정

0. 노드 개수 크기의 부모 테이블을 자신의 값을 갖도록 초기화
1. 합집합 Union 연산을 확인하여 서로 연결된 두 노드 A, B를 확인

• A와 B의 루트 노드 A’, B’를 각각 찾는다
• A’를 B’의 부모 노드로 설정한다

2. 모든 합집합 Union 연산을 처리할 때까지 1번 과정 반복

#예시

Union(1, 4) Union(2, 3) 처리

• 노드1과 노드4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정
• 노드2와 노드3의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 3이므로 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정

Union(2, 4) 처리

• 노드2와 노드4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 루트 노드2의 부모를 1로 설정

Union(5, 6) 처리 (생략)

 

 

루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야한다. 루트 노드의 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다.

import java.io.*;
import java.util.*;

public class Main {
    static int v, e;
    static int[] parent = new int[100001]; // 노드의 개수는 최대 100,000개라고 가정

    // 특정 원소가 속한 집합 찾기
    public static int findParent(int x) {
          // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적 호출
        if(parent[x] == x) return x;
        return parent[x] = find_parent(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;
    }

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

        v = sc.nextInt();
        e = sc.nextInt();

        for (int i = 1; i <= v; i++)
            parent[i] = i;

        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            unionParent(a, b);
        }

        // 생략


    }
}

경로압축

Find 함수를 최적화하기 위해 경로압축(Path Compression)을 이용할 수 있다. Find함수를 재귀적으로 호출한 뒤 부모 테이블 값을 바로 갱신한다.

public static int findParent(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find_parent(parent[x]);
}

경로 압축 기법을 적용하면 각 노드에 Find함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 된다. 따라서 시간복잡도가 개선된다.

---

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

서로소 집합은 무방향 그래프에서의 사이클(Cycle)을 판별할 때 사용한다.

💡 방향 그래프에서의 사이클 여부는 DFS

 

1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인

• 루트 노드가 서로 다르다면 두 노드에 대하여 Union 연산 수행
• 루트 노드가 서로 같다면사이클이 발생한 것

2. 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복

import java.io.*;
import java.util.*;

public class Main {
    static int v, e;
    static int[] parent = new int[100001]; // 노드의 개수는 최대 100,000개라고 가정

    // 특정 원소가 속한 집합 찾기
    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;
    }

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

        v = sc.nextInt();
        e = sc.nextInt();

        boolean cycle = false;

        for (int i = 1; i <= v; i++)
            parent[i] = i;

        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            if (findParent(a) == findParent(b)) {
                cycle = true;
                break;
            } else
                unionParent(a, b);
        }

        // 생략


    }
}