[알고리즘] 유니온 파인드(Union-Find)

1. 유니온 파인드(Union-Find)란 

여러 개의 노드가 존재할 때, 두 개의 노드를 선택, 현재 이 두 노드가 서로 같은 그래프에 속하는 지를 판별하는 알고리즘이다.

 

2. 특징

• 합집합 찾기
• union연산과 find연산으로 구성되어 있는 알고리즘으로 
  • union : 여러 노드가 있는 경우, 특정 노드 2개를 연결하여 1개의 집합으로 묶는 연산
    • 각 집합이 부모의 값을 얻어와서 한 쪽 부모가 다른 쪽 부모를 가리키게 만든다. (== 한개의 부모만 있는 집합을 만든다.)
    • 주로 더 작은 쪽으로 합친다.
    • a가 A의 요소이고 b가 B의 요소일 때, union(a, b)는 A U B를 뜻한다.
  • find : 두 노드가 같은 집합에 속해 있는 지 확인하는 연산
    • A와 B의 부모를 구했을 때, 같은 부모를 가리킨다면 같은 집합, 다른 부모를 가리키면 다른 집합이라고 판단한다.
    • 자식 노드는 항상 부모 노드를 가리키고 있어야 연산 속도가 빠르기 때문에 find연산 시 부모 노드의 값을 넣어줘야 한다.
    • a ∈ A일 때, find(a)는 A집합의 대표 노드를 리턴한다.

 

3. 알고리즘 로직

1. 제일 처음에는 각 노드들이 연결되어 있지 않기 때문에 대표 노드는 자기 자신이다

    - 1차원 배열을 각 노드의 값을 자기 인덱스 값으로 초기화한다.

2. 노드 2개를 선택하여, 각각의 대표 노드를 찾아 연결한다.(union연산)

    - 예를 들어 union(1, 4), union(5, 6)을 한다면 배열은 아래와 같아지겠다.

3. find연산

    - find연산은 자신이 속해있는 집합의 대표 노드를 찾는 연산임 뿐만 아니라 

    - 그래프 정돈 및 시간 복잡도를 향상 시킨다.

    - find연산의 동작 원리는 아래와 같다.

        1) 노드 배열에 인덱스와 대표노드의 값이 같은 지 확인한다.

        2) 같지 않으면 값이 가리키는 인덱스를 찾아간다.

        3) 인덱스와 대표 노드가 같을 때까지 1) ~ 2)를 반복한다 - 재귀로 구현

        4) 인덱스와 대표 노드가 같아진 경우, 재귀함수를 빠져 나오면서 거치는 모든 노드의 값을 루트 노드(3)에서 찾은 마지막 대표 노드)로 변경한다. 

4. 알고리즘 구현 코드

import java.util.Arrays;

public class UnionFindEx {
    public static void main(String[] args) {
        int[] parent = new int[11];
        for (int i = 1; i < parent.length; i++) {
            parent[i] = i;
        }

        union(parent, 1, 2);
        union(parent, 2, 4);
        union(parent, 5, 6);
        union(parent, 7, 10);
        union(parent, 1, 7);
        union(parent, 2, 6);

        System.out.println("====================");
        System.out.println(Arrays.toString(parent));

        StringBuilder sb = new StringBuilder();
        sb.append("1과 5는 같은 집합인가? ---> ").append(find(parent, 1) == find(parent, 5) ? "YES" : "NO").append("\n");
        sb.append("1과 10는 같은 집합인가? ---> ").append(find(parent, 1) == find(parent, 10) ? "YES" : "NO").append("\n");
        sb.append("2과 5는 같은 집합인가? ---> ").append(find(parent, 2) == find(parent, 5) ? "YES" : "NO").append("\n");
        sb.append("1과 7는 같은 집합인가? ---> ").append(find(parent, 1) == find(parent, 7) ? "YES" : "NO").append("\n");
        sb.append("3과 7는 같은 집합인가? ---> ").append(find(parent, 3) == find(parent, 7) ? "YES" : "NO").append("\n");
        sb.append("3과 10는 같은 집합인가? ---> ").append(find(parent, 3) == find(parent, 10) ? "YES" : "NO").append("\n");
        sb.append("7과 10는 같은 집합인가? ---> ").append(find(parent, 7) == find(parent, 10) ? "YES" : "NO").append("\n");

        System.out.println(sb);

    }

    private static void union(int[] parent, int a, int b) {
        a = find(parent, a);
        b = find(parent, b);

        // 이미 같은 부모를 가지고 있으면 그냥 리턴
        if(a == b) return;

        // 부모가 다른 경우 더 작은 값을 부모노드로..
        if (a > b) parent[a] = b;
        else parent[b] = a;
    }

    private static int find(int[] parent, int x) {
        /**
         * 예를 들어 find(parent, 10)인 경우
         * 10의 부모는 7 -> 7을 찾아보니 7도 다른 부모를 가지고 있다
         * find(parent, 7)을 하니까 7의 부모는 1
         * find(parent, 1)을 하니까 1의 부모는 1
         * => 1을 리턴해준다.
         * 
         * 이 로직을 코드로 구현하면 아래와 같다.
         */
        
        if(parent[x] == x) return x;
        else return find(parent, parent[x]);
    }
}

 

5. 유니온 파인드 문제 풀이

[백준][골드][UnionFind] - 1717 집합의 표현

---

그래프(Graph)