유니온 파인드 알고리즘 (Union-find)

유니온 파인드 알고리즘이란?

💡 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.

 

왜 이름이 유니온 파인드 인가?

유니온 파인드 알고리즘은 두 가지의 연산을 진행한다. 이 연산 과정을 Union, Find 라고 한다.

• Union : 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산이다, 즉 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 연산은 합집합 연산과 같다.
• Find : 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산이다.

크루스칼 알고리즘과 프림 알고리즘을 알기 위해서는 유니온 파인드 알고리즘을 알아야 한다.

 

유니온 파인드의 핵심 이론

유니온 파인드는 union, find 연산을 완벽히 이해하는 것이 핵심이다.

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a,b가 a ∈ A, b ∈ B 일 때, union(a,b)는 A ∪ B를 말한다.
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a 가 a ∈ A 일 때, find(a)는 A 집합의 대표 노드를 반환한다.

 

관련 문제

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

 

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

public class Main {
    static int n;
    static int m;
    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());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        parent = new int[n + 1];

        // 자기 자신으로 초기화
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            int third = Integer.parseInt(st.nextToken());

            if (first == 0) {
                union(second, third);
            } else {
                if(checkSame(second,third)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }

    }

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

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

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

    private static boolean checkSame(int a, int b) {
        a = find(a);
        b = find(b);

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