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

※ 본문은 혼자 공부한 내용을 기록한 글입니다. 오개념이 있다면 반드시 댓글로 알려주세요!

 

 

[ 1 ] 유니온 파인드(Union-Find)란?

유니온 파인드는 그래프에서 두 정점이 같은 집합에 속해 있는지 판별하는 알고리즘이다. 서로 연결되어 있지 않은 정점들도 판별할 수 있기에 서로소 집합(Disjoint-set) 이라고도 한다.

 

 

알고리즘 이름에 나와있듯이 특정 2개의 정점을 연결해 1개의 집합으로 묶는 union 연산(합집합)과 두 정점이 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있다.

 

 

DFS로도 각 정점이 연결되어 있는지 확인할 수 있겠지만, 경로가 길거나 확인해야 할 테스트 케이스가 많다면 시간 제한이 걸릴 수 있으므로 긴 경로를 축소할 수 있는 유니온 파인드를 활용해보자.

 

 

---

① 유니온 파인드는 일반적으로 1차원 배열로 표현한다.

처음 그래프가 주어졌을 땐 노드들이 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 그러므로 배열을 인덱스 값으로 초기화하자.

parent = new int[n+1];
for(int i = 1; i < n+1; i++) {
        parent[i] = i;
}

 

 

② union과 find 연산

union 연산은 연결하려는 노드들의 대표 노드를 찾아 연결한다. 즉, '대표 노드'끼리 연결하는 것이며, 대표 노드를 찾을 때 사용되는 연산이 find 이다.

static void union(int a, int b) {
    a = find(a);
    b = find(b);

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

static int find(int a) {
    if(a == parent[a]) {
        return a;
    }
    else {
        return parent[a] = find(parent[a]);
    }
}

 

find 연산은 대표 노드를 찾을 뿐만 아니라 그래프를 정돈하고 시간 복잡도를 향상시킨다. find 연산은 재귀 함수이며 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드의 값을 루트 노드로 변경한다. 이를 통해 find 연산을 거치는 노드들이 대표 노드와 바로 연결되고, 이후 모든 노드와 관련된 find의 연산 속도는 O(1)이 된다.

 

 

대표 노드와 바로 연결되지 않으면 어떻게 될까?

[ 1 - 2 - 3 - 4 - 5 - 6 ] 으로 연결된 그래프가 있다고 가정하자. parent 배열의 값은 인덱스 순서대로 [ 1 - 1 - 2 - 3 - 4 - 5 ] 가 될 것이다. 연속적인 find 연산을 통해 모든 노드가 연결되어 있음을 확인할 순 있겠지만 최악의 경우 find 연산의 시간복잡도는 O(n) 이 된다.

 

 

반면, find 연산을 거치는 노드들이 대표 노드와 바로 연결되도록 하면 parent 배열의 값은 인덱스 순서대로 [ 1 - 1 - 1 - 1 - 1 - 1 ] 이 될 것이며 O(1)의 시간복잡도로 find 연산을 수행할 수 있다.

 

 

---

[ 2 ] 예제 - 백준 1717번

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

대표적인 예제에 직접 유니온 파인드를 활용해보자!

 

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

public class Main {

    static int[] parent;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        parent = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(t == 0) {
                union(a, b);
            }

            else if(t == 1) {
                System.out.println(check(a, b));
            }
        }

    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

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

    static int find(int n) {
        if(n == parent[n]) {
            return n;
        }
        else {
            return parent[n] = find(parent[n]);
        }
    }

    static String check(int a, int b) {
        a = find(a);
        b = find(b);

        if(a == b) {
            return "YES";
        }
        else {
            return "NO";
        }
    }

}