서로소 집합(Union-Find) 자료구조의 이해

서로소 집합(Disjoint Set) 또는 유니온-파인드(Union-Find)는 그래프 이론에서 두 원소가 동일한 집합에 속하는지 판별하거나, 동적 연결 상태를 관리하는 데 특화된 자료구조입니다.

핵심 원리 및 동작 방식

1차원 배열을 사용하여 트리 구조를 표현하며, 각 인덱스는 노드를 의미하고 저장된 값은 해당 노드의 부모를 나타냅니다. 초기 상태에서는 모든 노드가 독립적인 집합이므로 자기 자신을 루트(부모)로 설정합니다.

• 경로 압축(Path Compression): Find 연산을 수행하는 과정에서 만나는 모든 노드가 직접 루트 노드를 가리키도록 배열을 갱신합니다. 이를 통해 트리의 높이를 낮추어 후속 탐색 시 시간 복잡도를 획기적으로 줄일 수 있습니다.
• 집합 합치기(Union): 두 노드를 같은 집합으로 병합할 때는 각 노드의 루트를 먼저 찾은 뒤, 한쪽 루트를 다른 쪽 루트의 자식으로 연결해야 합니다. 노드 자체를 직접 연결하면 트리 구조가 깨지므로 주의해야 하는 일반적인 실수 중 하나입니다.

주요 기능

• Find: 임의의 노드가 속한 집합의 루트 노드를 탐색합니다.
• Union: 두 노드가 속한 집합을 하나로 병합합니다.
• IsConnected: 두 노드의 루트가 동일한지 비교하여 같은 집합에 속하는지 확인합니다.

경로 존재 여부 판별 알고리즘 구현

두 정점 사이에 경로가 존재하는지 확인하는 문제는 결국 두 정점이 동일한 연결 요소(Connected Component)에 속하는지 판별하는 것과 동일합니다. 간선 정보를 입력받을 때마다 유니온 연산을 수행하고, 최종적으로 시작점과 도착점의 루트 노드를 비교하여 경로 존재 여부를 효율적으로 도출할 수 있습니다. 아래는 입출력 성능을 고려하여 BufferedReader를 활용하고 클래스 구조로 분리한 구현 코드입니다.

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

public class Main {
    private 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 nodeCount = Integer.parseInt(st.nextToken());
        int edgeCount = Integer.parseInt(st.nextToken());
        
        parent = new int[nodeCount + 1];
        for (int i = 1; i <= nodeCount; i++) {
            parent[i] = i;
        }
        
        for (int i = 0; i < edgeCount; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            unionNodes(u, v);
        }
        
        st = new StringTokenizer(br.readLine());
        int startNode = Integer.parseInt(st.nextToken());
        int endNode = Integer.parseInt(st.nextToken());
        
        if (findRoot(startNode) == findRoot(endNode)) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
    
    private static int findRoot(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = findRoot(parent[x]);
    }
    
    private static void unionNodes(int x, int y) {
        int rootX = findRoot(x);
        int rootY = findRoot(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
}

재사용 가능한 유니온-파인드 클래스 템플릿

실전 코딩 테스트나 프로젝트에서 즉시 활용할 수 있도록 캡슐화한 클래스 템플릿입니다. 찾기, 병합, 연결 여부 확인 기능을 메서드로 분리하여 가독성과 재사용성을 높였습니다.

public class UnionFind {
    private int[] roots;

    public UnionFind(int size) {
        roots = new int[size];
        for (int i = 0; i < size; i++) {
            roots[i] = i;
        }
    }

    public int getRoot(int node) {
        if (roots[node] == node) {
            return node;
        }
        // 경로 압축 적용
        return roots[node] = getRoot(roots[node]); 
    }

    public void merge(int nodeA, int nodeB) {
        int rootA = getRoot(nodeA);
        int rootB = getRoot(nodeB);
        
        if (rootA != rootB) {
            roots[rootB] = rootA;
        }
    }

    public boolean areConnected(int nodeA, int nodeB) {
        return getRoot(nodeA) == getRoot(nodeB);
    }
}