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

유니온 파인드는 앞에서 공부한 최단 경로 탐색 알고리즘과 맥락을 달리하는 그래프 문제입니다. 최단 경로 탐색 알고리즘은 여러 노드와 간선 정보가 주어졌을 때 특정 노드에서 다른 노드로 이동하는데 얼마나 적은 비용으로 이동할 수 있는지 비용을 최소화 시키는 것을 목적으로 한다면 유니온 파인드 알고리즘은 노드간 연결 관계를 파악하고 특정 간선을 연결할 시 노드 연결관계가 어떻게 변화하는지 파악하는 알고리즘입니다.

예를 들어 설명하도록 하겠습니다. 어느 나라에 여러 도시들이 있었는데 도로가 하나도 안깔려있어서 서로 단절되어 있었습니다. 도시를 연결해야겠다고 생각한 한 사람이 도시 사이에 도로를 놓기로 했습니다. 하지만 어떤 도시들 사이에는 산이 있어서 직접 도로를 못 놓는 경우도 있었기 때문에 연결이 가능한 지역은 한정적입니다. 그리고 예산이 충분하지 않기 때문에 우회하는 길이라도 이미 도시간 연결이 되어 있다면 도로를 깔지 않기로 했습니다.

위와 같은 경우가 바로 유니온 파인드 알고리즘을 사용해야 하는 문제입니다. 단절된 도시 하나하나는 노드를 의미하고, 도로는 간선을 의미합니다. 도로를 깔 때 우회도로라도 있다면 도로를 깔지 않겠다고 한 것은 파인드 알고리즘을 사용하여 도시간 연결관계를 파악하고, 만일 도시가 연결되어 있지 않는 경우에만 유니온을 할 것이라는 것을 의미합니다.

그렇다면 실제로 파인드와 유니온이 어떻게 실행되는지 알아보겠습니다. 유니온 파인드 알고리즘에서는 유니온이 일어날 때마다 연결되는 쪽의 부모 노드 정보를 갱신하게 됩니다. 새롭게 연결되는 노드는 자신의 부모노드 정보를 업데이트함으로써 기존 노드정보에 편입되게 됩니다. 파인드는 비교하려는 두 노드들이 같은 부모노드를 갖고 있는지 확인하는 것입니다. 정확히는 부모노드들의 최종적인 부모인 루트노드를 비교함으로써 같은 루트를 갖고 있다면 이미 연결된 것으로 판단하게 됩니다. 부모의 부모노드를 찾아가는 과정은 재귀함수를 사용하여 구현합니다.

이제 문제를 풀면서 이해해보도록 하겠습니다.

1717번: 집합의 표현 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
    private static int[] par;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        st = new StringTokenizer(br.readLine().trim());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        par = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            par[i] = i;
        }
 
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine().trim());
 
            int s = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            if (s == 0) {
                union(a, b);
            } else {
                int p = find(a);
                int q = find(b);
 
                if (p == q)
                    System.out.println("YES");
                else
                    System.out.println("NO");
            }
        }
    }
 
    private static void union(int a, int b) {
        int p = find(a);
        int q = find(b);
        
        if (p == q)
            return;
        
        par[q] = p;
    }
 
    private static int find(int n) {
        if (par[n] == n)
            return n;
        return par[n] = find(par[n]);
    }
}