유니온 파인드(Union-Find)

유니온 파인드란?

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

 

union & find 연산

- union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산

- find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

 

 

유니온 파인드의 원리

1. 유니온 파인드를 표현하는 일반적 방법은 1차원 배열을 이용하는 것

대표 노드를 저장하는 배열

 

-> 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드

-> 각 노드가 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화 됨

 

 

2. 2개의 노드를 선택해 각각 대표 노드를 찾아 연결하는 union 연산 수행

* 작은 수를 대표 노드라고 가정

 

2.1 union(1, 4) : 1번과 4번 노드의 대표 노드인 1을 배열에 넣어줌

2.2 union(5, 6) : 5번과 6번 노드의 대표 노드인 5를 배열에 넣어줌

2.3 union(4, 6) : 4번과 6번 노드의 union 연산은 각 대표 노드를 찾고(find 연산) union(1, 5)를 수행 -> 배열 5번째 자리에 대표 노드인 1이 들어감

 

 

3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산

-> 단순 대표 노드를 찾는 역할 뿐 아니라 그래프를 정돈하고 시간 복잡도를 향상시킴

 

 

find 연산 작동 원리

1. 대상 노드 배열의 index와 value가 동일한지 확인

2. 동일하지 않으면 value값이 가리키는 index 위치로 이동

3. index값과 value값이 같을 때까지(대표 노드를 찾을 때까지) 1~2번 반복 -> 재귀 함수 사용

4. 대표 노드 도달 시 재귀 함수를 빠져나며 거친 모든 노드값을 루트 노드값으로 변경

 

 

예시 : find(6)

 

 

-> 연산 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경

-> 추후 노드와 관련된 find 연산 속도가 O(1)로 변경됨

 

 

-> 위 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타남

-> 이후 find(4) 연산 수행 시 한 번의 이동으로 바로 대표 노드를 찾을 수 있음

---

백준 온라인저지 1717번

import java.util.Scanner;

public class P1717_집합표현하기 {

    static int parent[];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 원소 개수
        int M = sc.nextInt(); // 질의 개수
        parent = new int[N+1]; // 대표 노드 저장 배열

        // 대표 노드를 자기 자신으로 초기화
        for(int i=0; i<parent.length; i++) {
            parent[i] = i;
        }

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

            if(question == 0) {
                // union 연산
                union(a, b);
            } else {
                // find 연산
                boolean result = checkSum(a, b);

                if(result) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    private static void union(int a, int b) {
        // 1. a와 b의 대표 노드 찾기
        a = find(a);
        b = find(b);

        // 2. 연결
        if(a != b) {
            parent[b] = a; // 둘을 연결
        }
    }

    private static int find(int a) {
        if(a == parent[a]) {
            // index와 value가 같으면 대표 노드
            return a;
        } else {
            // value를 index로 바꿔 다시 찾음(재귀의 형태)
            // 빠져나오며 a의 대표 노드값 저장!!! -> 경로 압축
            return parent[a] = find(parent[a]);
        }
    }

    // 입력받은 두 원소가 같은 집합인지 확인
    private static boolean checkSum(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) {
            return true;
        } else {
            return false;
        }
    }
}