[Algorithm] 유니온-파인드(Union-Find)

유니온-파인드(Union-Find)?

Union-Find는 여러 개의 노드가 존재할 때, 어떤 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

방법

같은 그래프에 속하는지 어떻게 판별할까? 다음 그림을 보고 쉽게 이해하자

먼저 8개의 노드가 위와 같이 있다고 가정한다.

각 노드는 자기 자신을 가리키며 이는 자기 자신이 곧 루트 노드임을 의미한다.

 

여기서 5와 2가 연결되었다고 해보자.

그럼 다음과 같이 표현할 수 있다.

5번 노드에 2번 노드를 가리키는 값 2가 들어간다.

일반적으로 합칠 때는 더 작은쪽으로 합치며 이를 Union이라 한다.

 

그 다음 2와 1이 연결되었다고 해보자.

2번 노드는 1번 노드를 가리키며 이를 의미하는 값 1이 들어간다.

 

그럼 여기서 5번과 1번이 같은 그래프에 속하는지 어떻게 판별할까?

바로 루트 노드를 확인하는 것이다. 이를 확인하기 위해 재귀적인 형태의 탐색이 필요하다

 

5번 노드의 부모 노드는 2번 노드이다. 하지만 2번은 부모 노드를 가지고 있으므로 루트 노드가 아니다.

여기서 한 번 더 들어가서 최종적으로 루트 노드를 찾으면 1번 노드가 5번 노드의 루트 노드임을 알 수 있다.

 

즉, 2번 노드의 부모 노드이자 루트 노드는 1이고, 5번 노드의 루트 노드도 1이므로 두 노드는 같은 그래프에 속한다고 볼 수 있다.

 

이렇게 탐색을 통해 루트 노드를 찾았으면 마지막으로 값을 갱신해준다.

이렇게 해서 1, 2, 5번 노드의 루트가 모두 1이기 때문에 같은 그래프에 속한다고 할 수 있다.

 

구현

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

        unionParent(parent, 1, 2);
        unionParent(parent, 2, 3);
        unionParent(parent, 3, 4);
        unionParent(parent, 5, 6);
        unionParent(parent, 6, 7);
        unionParent(parent, 7, 8);
        System.out.println("1과 5는 연결되어 있는가? " + findParent(parent, 1, 5));
        unionParent(parent, 1, 5);
        System.out.println("1과 5는 연결되어 있는가? " + findParent(parent, 1, 5));
    }

    public static int getParent(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }
        // 부모를 탐색하면서 루트를 찾으면 값을 모두 루트로 갱신한다.
        return parent[x] = getParent(parent, parent[x]);
    }

    public static void unionParent(int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);

        if (a < b) {
            parent[b] = a;
            return;
        }
        parent[a] = b;
    }

    public static boolean findParent(int[] parent, int a, int b) {
        return getParent(parent, a) == getParent(parent, b);
    }
}

 

유니온 파인드와 관련된 문제를 풀어보고 싶다면 다음 링크를 참고하자

baekjoon 1717 - 집합의 표현

1717번: 집합의 표현

baekjoon 1976 - 여행 가자

1976번: 여행 가자