분리 집합 (Disjoint Set) 알고리즘 : Union-Find

분리 집합(Disjoint Set)은 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

---

Union-Find 원리 이해하기

1. Union-Find를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것
   • 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨
   • 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화

   

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행
   • 대표 노드가 아닌 경우에는 find 연산으로 대표 노드 찾아서 연결

   

3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산
   • 단순히 대표 노드만 찾는 역할이 아니라 그래프를 정돈하고 시간 복잡도를 향상 시킴

find 연산의 작동 원리

1. 대상 노드 배열에 index값과 value 값이 동일한지 확인
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동
3. 이동 위치의 index값과 value값이 같을 때까지 1~2 반복 (재귀)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 루트 노드 값으로 변경(경로 압축)

💡 Union-Find 에서 자주 실수하는 부분
1. find 연산을 수행할 때 재귀 함수에서 나오면서 탐색한 모든 노드와 대표 노드값을 이번 연산에서 발견한 대표 노드로 변경하는 부분
2. union 연산에서 실행된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분

---

분리 집합 핵심 코드

    private static int[] parents;

    private static int find(int n) {
        if (parents[n] == n) return n;
        return parents[n] = find(parents[n]);
    }
    private static boolean union(int n1, int n2) {
        int p1 = find(n1);
        int p2 = find(n2);

        if(p1 == p2) return false;

        parents[p2] = p1;
        return true;
    }

 

---

🚀 관련 문제 풀이

• [G5] BOJ_1717 : 집합의 표현 (23.03.08)
• [G4] BOJ_1043 : 거짓말 (23.06.09)
• [G4] BOJ_1647 : 도시 분할 계획 (24.03.14)
• [G4] BOJ_20040 : 사이클 게임 (24.03.29)
• [G4] BOJ_1976 : 여행 가자 (24.04.22)