[알고리즘] 유니온 파인드 알고리즘 (union-find)

union-find 알고리즘

위와 같은 그림에서 연결된 그래프의 집합을 찾아내는 알고리즘이다.
1은 7과 연결돼있고, 7은 6과 연결돼 있을 때, 1과 6이 연결됨을 쉽게 찾아낼 수 있는 알고리즘이다.
해당 알고리즘에는 두 가지 핵심 동작이 있다.

• union : 서로 다른 두 개의 집합을 하나의 집합으로 연결하는 동작이다.
• find : 어떤 원소가 어떤 집합에 속해있는지 확인하는 동작이다.
  보통 작은 수를 최상위 노드(root)로 설정한다.

초기 세팅

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

정점의 번호가 1 ~ N까지 있을 때, 해당 노드의 집합 번호를 저장하는 parent 배열을 만들고, 처음에는 자기 자신으로 초기화 한다.

find

현재 노드가 어떤 집합에 속해있는지 찾는 과정으로, 재귀적으로 탐색하여 최상위 노드를 찾는다.

public static int find(int[] parent, int x){
    if(parent[x] == x) return x;
    else return find(parent, parent[x]);
}

해당 예시에서

• 6의 집합을 찾는다고 하면, 6 -> 7 -> 1 이렇게 탐색하여 1을 찾을 것이다.
• 3의 집합을 찾는다면 3 -> 1 이렇게 탐색하여 1을 찾을 것이다.
• 4의 집합을 찾는다면 4 -> 2 이렇게 탐색하여 2를 찾을 것이다.
• 2의 집합을 찾는다면 2를 찾을 것이다.

union

두 노드를 하나의 집합으로 만들어주는 과정이다.
두 노드의 최상위 노드를 찾고, 그 최상위 노드를 연결시켜준다.

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

    int min = Math.min(a, b);

    parent[a] = min;
    parent[b] = min;
}

일단 a와 b의 최상위 노드를 find()를 활용하여 찾는다.
그리고 두 노드 중 값이 작은 것을 최상위 노드로 하여 parent에 값을 저장해준다.
과정을 한번 보자.

• 초기 상태
  
  모든 노드의 부모는 자기 자신이다.
  
  
• 1 - 3 union
  
  1의 root인 1과 3의 root인 3 중 더 작은 1을 루트로 지정한다.
  
  
• 7 - 6 union
  
  6의 root인 6과 7의 root인 7 중 더 작은 6을 루트로 지정한다.
  
  
• 3 - 7 union
  
  3의 root는 1이고, 7의 root는 6이다. 1과 6 중 더 작은 1을 루트로 지정한다.
  
  이제 7의 root를 찾으려면 7 -> 6 -> 1 이렇게 된다.
  
  
• 4 - 2 union
  
  4의 root인 4와 2의 root인 2 중 더 작은 2를 루트로 지정한다.
  
  최종
  
  이렇게 모양을 만들어 놓으면, 7과 3이 같은 집합인가? 를 따져볼 때,
  find연산만 진행하여 7과 3의 root가 같은지만 확인하면 된다.
  ( 7 -> 6 -> 1 ) == ( 3 -> 1 )

관련 문제

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

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 0 -> union / 1 -> find
public class Main {

    public static int find(int[] parent, int x){
        if(parent[x] == x) return x;
        else return find(parent, parent[x]);
    }

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

        int min = Math.min(a, b);

        parent[a] = min;
        parent[b] = min;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int size = Integer.parseInt(stringTokenizer.nextToken());

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

        for(int i = 0; i < size; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int command = Integer.parseInt(stringTokenizer.nextToken());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());

            if(command == 0){
                union(parent, a, b);
            }
            else{
                if(find(parent, a) == find(parent, b)) System.out.println("YES");
                else System.out.println("NO");
            }
        }
    }
}