[알고리즘 / JAVA] 유니온 파인드(Union-Find) 완전 정복 – 집합의 연결 관계 이해

heon.blog·2025년 6월 8일

알고리즘 / JAVA

목록 보기

7/8

1. 개요

유니온 파인드(Union-Find)는 서로소 집합(Disjoint Set) 자료구조라고도 하며,
여러 개의 원소를 여러 집합으로 나누어 관리합니다.
이를 통해 두 원소가 같은 집합에 속하는지 빠르게 확인할 수 있고, 서로 다른 집합을 하나로 합치는 연산도 효율적으로 처리할 수 있습니다.

2. 유니온 파인드란?

union(x, y): 두 원소 x와 y가 속한 집합을 합친다.
find(x): 원소 x가 속한 집합의 대표자(루트)를 찾는다.

집합의 대표자(루트)를 찾음으로써 두 원소가 같은 집합인지 확인할 수 있습니다.

유니온 파인드는 다음과 같은 문제에서 매우 유용합니다.

네트워크 연결 여부 확인: 두 컴퓨터가 같은 네트워크 상에 있는지 확인
친구 관계 그래프: 두 사람이 친구 그룹에 속해 있는지 확인
사이클 탐지: 그래프에서 사이클이 형성되는지 여부 검사
최소 신장 트리(MST) 알고리즘: 크루스칼 알고리즘에서 사이클 여부 확인에 필수

예시 )
사람들의 친구 관계를 관리할 때 각 사람을 노드로 보고, 친구 관계를 union 연산으로 묶어 나가면, 특정 두 사람이 같은 친구 그룹에 있는지 find 연산을 통해 쉽게 판단할 수 있습니다.

3. 유니온 파인드 핵심 개념

3-1. 경로 압축 (Path Compression)

find(x) 연산을 수행할 때, x의 부모 노드를 따라 루트 노드를 찾게 되는데, 이 과정에서 방문한 모든 노드의 부모를 루트로 직접 연결합니다.
이렇게 하면 모든 노드가 루트에 직접 연결되기 때문에, 다음 find 연산은 거의 한 번만에 루트를 찾을 수 있게 됩니다.

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 경로 압축
    }
    return parent[x];
}

예시 )
초기 상태: 1 → 2 → 3 (3이 루트)
find(1)을 호출하면: 1 → 3, 2 → 3 으로 갱신됨 (모두 루트로 직접 연결됨)

3-2. 높이 또는 크기 기반 합치기 (Union by Rank / Size)

두 트리를 합칠 때, 트리의 높이(랭크)나 노드 개수(크기)를 기준으로 작은 쪽을 큰 쪽에 붙입니다.
이렇게 하면 전체 트리의 최대 깊이가 불필요하게 증가하는 것을 방지할 수 있어, find 연산 시 루트까지 올라가는 시간이 줄어듭니다.
즉, 트리가 한쪽으로 길게 자라는 것을 막아 시간 복잡도를 O(α(N))(거의 상수 시간)으로 유지할 수 있습니다.

public void union(int x, int y) {
    int xRoot = find(x);
    int yRoot = find(y);

    if (xRoot == yRoot) return;

    if (rank[xRoot] < rank[yRoot]) {
        parent[xRoot] = yRoot;
    } else {
    	parent[yRoot] = xRoot;
        if (rank[xRoot] == rank[yRoot]) {
            rank[xRoot]++;
        }
    }
}

예시 )
x 트리의 높이가 1이고 y 트리의 높이가 2일 때,
x를 y에 붙이면 전체 트리의 높이는 그대로 2로 유지됩니다.
반대로 y를 x에 붙이면 트리의 높이가 3으로 불필요하게 증가하게 되어, 탐색 시간이 더 오래 걸리게 됩니다.

4. 유니온 파인드 구현 방법 (Java)

import java.util.*;

public class UnionFind {
    static int[] parent;
    static int[] rank;  // 각 노드의 랭크(트리 높이) 저장

    public static void main(String[] args) {
        int n = 7; // 노드 개수
        parent = new int[n + 1];
        rank = new int[n + 1];

        // 초기화: 각 노드는 자기 자신을 부모로, 랭크는 0으로 초기화
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        // union 연산 수행
        union(1, 2);
        union(2, 3);
        union(4, 5);
        union(6, 7);
        union(5, 6);

        // 같은 집합인지 확인
        System.out.println(find(1) == find(3)); // true
        System.out.println(find(1) == find(4)); // false
        System.out.println(find(5) == find(7)); // true
    }

    // find 연산 (경로 압축 적용)
    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // union 연산 (Union by Rank 적용)
    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
            	rank[rootX]++;
            }
        }
    }
}

다음은 union 연산의 동작 과정입니다.

union(1, 2)

find(1) → 1, find(2) → 2 (서로 다른 집합)
rank[1] = rank[2] 이므로
1을 루트 노드로 설정하고 2를 연결, rank[1]++

parent: [0, 1, 1, 3, 4, 5, 6, 7]
rank: [0, 1, 0, 0, 0, 0, 0, 0]

union(2, 3)

find(2) → 1, find(3) → 3
rank[1] > rank[3] 이므로 3을 {1, 2} 집합에 붙임

parent: [0, 1, 1, 1, 4, 5, 6, 7]
rank: [0, 1, 0, 0, 0, 0, 0, 0]

union(4, 5)

find(4) → 4, find(5) → 5
rank[4] = rank[5] 이므로
4를 루트 노드로 설정하고 5를 연결, rank[4]++

parent: [0, 1, 1, 1, 4, 4, 6, 7]
rank: [0, 1, 0, 0, 1, 0, 0, 0]

union(6, 7)

find(6) → 6, find(7) → 7
rank[6] = rank[7] 이므로
6을 루트 노드로 설정하고 7을 연결, rank[6]++

parent: [0, 1, 1, 1, 4, 4, 6, 6]
rank: [0, 1, 0, 0, 1, 0, 1, 0]

union(5, 6)

find(5) → 4, find(6) → 6
rank[4] = rank[6] 이므로
4를 루트 노드로 설정하고 6을 연결, rank[4]++

parent: [0, 1, 1, 1, 4, 4, 4, 6]
rank: [0, 1, 0, 0, 2, 0, 1, 0]

결과적으로 union() 연산을 통해 {1, 2, 3}, {4, 5, 6, 7} 두 개의 집합이 형성되고,
find() 연산을 통해 두 노드가 같은 집합에 속하는지 확인할 수 있게 됩니다.

5. 백준 문제 추천

사이트	문제명	설명
백준 1717	집합의 표현	유니온 파인드 기본 문제
백준 1976	여행 가자	연결 여부 판단 문제
백준 4195	친구 네트워크	문자열 매핑 + 유니온 파인드 활용