[유니온 파인드 (Union-Find)] 서로소 집합 알고리즘

서로소 집합 (Disjoint-set)

서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다.

• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.
  이를 대표자(representative) 라고 한다.
• 서로소 집합을 표현하는 방법
  • 연결 리스트
  • 트리
• 서로소 집합 연산
  • Make-Set(x)
  • Find-Set(x)
  • Union(x,y)

---

서로소 집합 표현 - 연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
• 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.

서로소 집합 표현 - 트리

• 같은 집합의 원소들을 하나의 트리로 표현한다.
  • 각 노드가 자신의 부모노드를 기억 (저장)
• 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

---

서로소 집합에 대한 연산 (유니온-파인드)

각 집합이 어디에 속하는지 find 하고
다른 집합들을 union 하기 때문에 Union-Find 알고리즘이라고 불린다.

Make-Set(x)
유일한 멤버 x 를 포함하는 단위 집합을 생성하는 연산 (딱 한 번, 전처리 수행)

static int[] parent = new int[N];
static void makeSet() {		// 모두가 서로소인 원소 1개를 갖는 집합 배열 구조
	for (int i=0; i<=N; i++) {
    	parent[i] = i;
	}
}

Find-Set(x)
x 를 포함하는 집합을 찾는 연산

static int findSet(int x) {
	if (parent[x] == x)
    	return x;
	else
    	return findSet(parent[x]);

Union(x,y)
x와 y를 포함하는 두 집합을 통합하는 연산

static void union(int x, int y) {
	int px = findSet(x);
    int py = findSet(y);
    // 어떻게 합칠 것인가?
    // #1) 앞인 x 가 부모가 되도록
	parent[py] = px;
	// #2) 크기를 비교해서 정한다
    if (px < py)
    	parent[py] = px;
	else
    	parent[px] = py;
}

union 성공 여부에 따라 boolean 을 return 하도록 변형

static boolean union(int x, int y) {
	int px = findSet(x);
    int py = findSet(y);
    if (px == px)
    	return false;	// 이미 같은 집합이므로 union 불가
    // 어떻게 합칠 것인가?
    // #1) 앞인 x 가 부모가 되도록
	parent[py] = px;
	// #2) 크기를 비교해서 정한다
    if (px < py)
    	parent[py] = px;
	else
    	parent[px] = py;
	return true;		// union 성공
}

---

연산의 효율을 높이는 방법

Path Compression

• Find-Set 을 행하는 과정에서 만나는 모든 노드들이 직접 root 를 가리키도록 포인터를 바꾸어 준다.
  • Find Set 과정에서 만나는 노드들만 경로압축이 이뤄진다.
  • 형제노드는 Find Set 과정에서 만나지 않아서 그대로 상태가 유지된다.

Path Compression 을 적용한 Find-Set 연산

변경 전

Find-Set(x)
	if (x == p[x]) : return x					// 본인이 루트
    else :			 return Find-Set(p[x])

변경 후

Find-Set(x)
	if (x == p[x]) : return x
    else : 			 return p[x] = Find-Set(p[x])		// path 압축

=> 무조건 하는게 좋음

---

유니온 파인드 활용 알고리즘 문제

백준 1717 : 집합의 표현

문제

초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

---

답안 코드

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

class Main {
    
    static int N, M;
    static int[] parent;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // makeSet
        parent = new int[N+1];
        makeSet();
        
        // 시뮬레이션
        for (int m=0; m<M; m++) {
            st = new StringTokenizer(br.readLine());
            int oper = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if (oper == 0) {    // union
                union(a,b);
            } else if (oper == 1) {     // check if(findSet(a)==findSet(b))
                if (findSet(a) == findSet(b)) {
                    sb.append("YES").append("\n");
                } else sb.append("NO").append("\n");
            }
        }
    
        System.out.println(sb);
    
    }
    
    static void makeSet() {
        for (int n=0; n<=N; n++) {
            parent[n] = n;
        }
    }
    
    static int findSet(int child) {
        if (child == parent[child]) return child;
        else return parent[child] = findSet(parent[child]);     // path 압축
    }
    
    static boolean union(int a, int b) {
        int parentA = findSet(a);
        int parentB = findSet(b);
        
        if (parentA == parentB) return false;
        else if (parentA < parentB) {
            parent[parentB] = parentA;
        } else {
            parent[parentA] = parentB;
        }
        
        return false;
    }
}

---

알고리즘에는 '분리집합'이라는 카테고리로 묶여 있는 듯 하다
[백준 분리집합 문제] https://www.acmicpc.net/problemset?sort=ac_desc&algo=81

---

TO DO

유니온 파인드 알고리즘 활용

• 크루스칼 알고리즘 (Kruskal Algorithm)
• 프림 알고리즘 (Prim Algorithm)

사실 이 유니온-파인드 알고리즘은 위의 두 MST 알고리즘의 선수과목이다.