[알고리즘] 24. 유니온 파인드(Union-Find)

지난 글에서는 그래프 기초에 대해 정리했습니다. 이번 글에서는 그래프와 집합 문제에서 자주 사용되는 유니온 파인드(Union-Find)에 대해 알아보겠습니다.

유니온 파인드는 여러 원소가 있을 때, 두 원소가 같은 집합에 속해 있는지 빠르게 확인하고, 서로 다른 집합을 하나로 합치는 자료구조입니다. 알고리즘 문제에서는 서로소 집합, 연결 여부 확인, 사이클 판별 문제에서 자주 등장합니다.

유니온 파인드는 여러 원소를 집합으로 관리하고, 같은 집합인지 빠르게 확인하는 자료구조입니다.

1. 유니온 파인드란?

유니온 파인드는 이름 그대로 두 가지 핵심 연산을 가지고 있습니다.

연산	의미
union	두 집합을 하나로 합친다.
find	어떤 원소가 속한 집합의 대표를 찾는다.

예를 들어 1, 2, 3, 4, 5라는 원소가 있다고 생각해보겠습니다. 처음에는 모두 서로 다른 집합에 속해 있습니다.

{1}, {2}, {3}, {4}, {5}

여기서 1과 2를 합치면 같은 집합이 됩니다.

{1, 2}, {3}, {4}, {5}

다시 2와 3을 합치면 1, 2, 3이 같은 집합이 됩니다.

{1, 2, 3}, {4}, {5}

이제 1과 3은 직접 합친 적이 없어도 같은 집합에 속해 있다고 판단할 수 있습니다.

유니온 파인드는 원소들이 서로 연결되어 있는지 확인하는 데 유용합니다.

2. 서로소 집합이란?

유니온 파인드는 서로소 집합을 표현할 때 자주 사용됩니다. 서로소 집합은 서로 공통 원소가 없는 집합을 의미합니다.

{1, 2, 3} 과 {4, 5}는 서로소 집합입니다.
두 집합 사이에 공통 원소가 없기 때문입니다.

알고리즘 문제에서는 여러 원소를 그룹으로 나누고, 어떤 두 원소가 같은 그룹인지 확인해야 하는 경우가 많습니다.

이때 유니온 파인드를 사용하면 집합을 효율적으로 관리할 수 있습니다.

3. 유니온 파인드가 필요한 상황

유니온 파인드는 아래와 같은 상황에서 자주 사용됩니다.

두 원소가 같은 집합에 속하는지 확인해야 할 때
여러 그룹을 합쳐야 할 때
그래프에서 두 정점이 연결되어 있는지 확인해야 할 때
무방향 그래프에서 사이클을 판별해야 할 때
최소 신장 트리 알고리즘인 크루스칼 알고리즘을 사용할 때
네트워크 연결 관계를 관리해야 할 때

문제를 보고 “같은 그룹인가?”, “연결되어 있는가?”, “두 집합을 합쳐야 하는가?”라는 느낌이 들면 유니온 파인드를 떠올리면 좋습니다.

유니온 파인드는 연결 여부와 그룹 합치기 문제에서 강력한 자료구조입니다.

4. parent 배열

유니온 파인드는 보통 parent 배열을 이용해 구현합니다. parent 배열은 각 원소의 부모를 저장하는 배열입니다.

처음에는 각 원소가 자기 자신을 부모로 가집니다.

원소:    1  2  3  4  5
parent: 1  2  3  4  5

이 상태는 모든 원소가 서로 다른 집합에 있다는 뜻입니다. 각 원소가 자기 자신을 대표로 가지고 있습니다.

int n = 5;
int[] parent = new int[n + 1];

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

정점 번호가 1부터 시작하는 문제에서는 배열 크기를 n + 1로 만드는 경우가 많습니다.

parent[i]는 i번 원소의 부모를 의미합니다.

5. 대표 원소

유니온 파인드에서 한 집합을 대표하는 원소를 대표 원소라고 합니다. 보통 parent를 계속 따라 올라갔을 때 자기 자신을 부모로 가지는 원소가 대표입니다.

parent[1] = 1
parent[2] = 1
parent[3] = 1

위 상태에서 1, 2, 3은 같은 집합입니다. 그리고 대표 원소는 1입니다.

2의 부모는 1이고, 3의 부모도 1입니다. 따라서 2와 3은 직접 연결되어 있지 않아도 같은 대표를 가지므로 같은 집합이라고 판단할 수 있습니다.

6. find 연산

find 연산은 어떤 원소가 속한 집합의 대표 원소를 찾는 연산입니다.

만약 자기 자신이 부모라면 그 원소가 대표입니다. 아니라면 부모를 계속 따라 올라가 대표를 찾습니다.

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

    return find(parent[x]);
}

이 코드는 x의 부모가 자기 자신이면 x를 반환합니다. 그렇지 않으면 parent[x]의 대표를 다시 찾습니다.

find는 어떤 원소의 최종 대표를 찾는 연산입니다.

7. find 동작 예시

다음과 같은 parent 관계가 있다고 하겠습니다.

parent[1] = 1
parent[2] = 1
parent[3] = 2

3의 대표를 찾으려면 다음 순서로 부모를 따라갑니다.

find(3)
→ parent[3] = 2
→ find(2)
→ parent[2] = 1
→ find(1)
→ parent[1] = 1
→ 대표는 1

따라서 3의 대표 원소는 1입니다.

즉 1, 2, 3은 모두 같은 집합에 속해 있습니다.

8. union 연산

union 연산은 두 원소가 속한 집합을 하나로 합치는 연산입니다.

두 원소의 대표를 각각 찾고, 대표가 다르다면 한쪽 대표를 다른 대표에 연결합니다.

public static void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rootA != rootB) {
        parent[rootB] = rootA;
    }
}

위 코드는 b가 속한 집합의 대표를 a가 속한 집합의 대표 아래로 연결합니다.

중요한 점은 a와 b를 바로 연결하는 것이 아니라, 각각의 대표 원소를 찾아서 대표끼리 연결한다는 것입니다.

union은 두 원소의 대표를 찾아 서로 다른 집합이면 하나로 합칩니다.

9. union 동작 예시

처음에는 모든 원소가 자기 자신을 부모로 가집니다.

원소:    1  2  3  4
parent: 1  2  3  4

union(1, 2)를 실행하면 1과 2가 같은 집합이 됩니다.

parent[2] = 1

원소:    1  2  3  4
parent: 1  1  3  4

이제 union(2, 3)을 실행하면 2와 3이 합쳐집니다. 하지만 2의 대표는 1이므로 3은 1 아래로 연결됩니다.

parent[3] = 1

원소:    1  2  3  4
parent: 1  1  1  4

결과적으로 1, 2, 3은 같은 집합이 됩니다.

10. 같은 집합인지 확인하기

두 원소가 같은 집합인지 확인하려면 find 결과를 비교하면 됩니다.

if (find(a) == find(b)) {
    System.out.println("같은 집합입니다.");
} else {
    System.out.println("다른 집합입니다.");
}

대표 원소가 같다면 같은 집합입니다. 대표 원소가 다르다면 서로 다른 집합입니다.

find(1) == find(3) → 같은 집합
find(1) != find(4) → 다른 집합

같은 집합인지 확인하는 핵심은 두 원소의 대표가 같은지 비교하는 것입니다.

11. 전체 기본 코드

유니온 파인드의 기본 구조를 Java 코드로 정리하면 다음과 같습니다.

public class Main {
    static int[] parent;

    public static void main(String[] args) {
        int n = 5;
        parent = new int[n + 1];

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

        union(1, 2);
        union(2, 3);

        System.out.println(find(1) == find(3));
        System.out.println(find(1) == find(4));
    }

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

        return find(parent[x]);
    }

    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }
}

출력 결과는 다음과 같습니다.

true
false

1과 3은 같은 집합이고, 1과 4는 다른 집합입니다.

12. 경로 압축

기본 find 연산은 부모를 계속 따라 올라가 대표를 찾습니다. 그런데 트리가 길게 늘어지면 find가 느려질 수 있습니다.

1 ← 2 ← 3 ← 4 ← 5

위 구조에서 find(5)를 하면 5 → 4 → 3 → 2 → 1 순서로 올라가야 합니다. 이런 경우가 반복되면 비효율적입니다.

이를 개선하기 위해 경로 압축을 사용합니다. 경로 압축은 find를 수행하면서 지나간 노드들을 바로 대표에 연결하는 방법입니다.

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

    parent[x] = find(parent[x]);
    return parent[x];
}

이렇게 하면 find를 한 번 수행한 뒤에는 다음부터 대표를 훨씬 빠르게 찾을 수 있습니다.

경로 압축은 find 과정에서 부모를 대표 원소로 바로 갱신해 탐색 속도를 개선합니다.

13. 경로 압축 동작 예시

다음처럼 부모 관계가 길게 이어져 있다고 하겠습니다.

parent[5] = 4
parent[4] = 3
parent[3] = 2
parent[2] = 1
parent[1] = 1

find(5)를 실행하면 최종 대표는 1입니다. 경로 압축을 적용하면 5, 4, 3, 2가 모두 바로 1을 가리키게 됩니다.

압축 전:
5 → 4 → 3 → 2 → 1

압축 후:
5 → 1
4 → 1
3 → 1
2 → 1

이렇게 구조가 납작해지기 때문에 이후 find 연산이 매우 빨라집니다.

14. 사이클 판별에 사용하기

유니온 파인드는 무방향 그래프에서 사이클을 판별할 때 사용할 수 있습니다.

간선을 하나씩 확인하면서 두 정점이 이미 같은 집합인지 검사합니다. 이미 같은 집합이라면 그 간선을 추가했을 때 사이클이 생깁니다.

간선: 1-2
간선: 2-3
간선: 1-3

1-2를 연결하면 1과 2가 같은 집합이 됩니다. 2-3을 연결하면 1, 2, 3이 같은 집합이 됩니다. 이제 1-3을 확인하면 이미 같은 집합입니다. 따라서 1-3 간선을 추가하면 사이클이 생깁니다.

int[][] edges = {
    {1, 2},
    {2, 3},
    {1, 3}
};

boolean hasCycle = false;

for (int i = 0; i < edges.length; i++) {
    int a = edges[i][0];
    int b = edges[i][1];

    if (find(a) == find(b)) {
        hasCycle = true;
        break;
    }

    union(a, b);
}

System.out.println(hasCycle);

출력 결과는 다음과 같습니다.

true

이미 같은 집합에 속한 두 정점을 다시 연결하면 사이클이 생깁니다.

15. 유니온 파인드가 자주 나오는 문제 유형

유니온 파인드는 아래 유형에서 자주 등장합니다.

문제 유형	유니온 파인드가 필요한 이유
집합 표현	여러 원소가 같은 집합인지 확인
네트워크 연결	컴퓨터나 노드가 서로 연결되어 있는지 확인
사이클 판별	이미 연결된 두 정점을 다시 연결하는지 확인
크루스칼 알고리즘	간선을 선택할 때 사이클 발생 여부 확인
친구 관계 그룹	같은 그룹에 속하는 사람들을 관리

특히 “같은 집합인지 확인하라”는 문장이 문제에 나오면 유니온 파인드를 의심해볼 수 있습니다.

16. 시간복잡도

경로 압축을 사용한 유니온 파인드는 매우 빠르게 동작합니다. 일반적인 알고리즘 문제에서는 find와 union을 거의 O(1)에 가깝게 생각하는 경우가 많습니다.

연산	의미	시간복잡도 느낌
find	대표 원소 찾기	매우 빠름
union	두 집합 합치기	매우 빠름

정확한 이론적 복잡도는 더 복잡하지만, 입문 단계에서는 경로 압축을 적용하면 매우 효율적으로 동작한다고 이해하면 충분합니다.

유니온 파인드는 많은 연결 확인과 집합 합치기를 빠르게 처리할 수 있습니다.

17. 유니온 파인드에서 자주 하는 실수

유니온 파인드를 구현할 때는 아래 실수를 조심해야 합니다.

parent 배열 초기화를 하지 않는 경우
find에서 종료 조건을 잘못 작성하는 경우
union에서 원소끼리 바로 연결하고 대표끼리 연결하지 않는 경우
정점 번호가 1부터 시작하는데 배열 크기를 n으로만 만드는 경우
경로 압축을 적용하지 않아 find가 느려지는 경우
같은 집합인지 확인할 때 parent[a] == parent[b]로만 비교하는 경우

특히 같은 집합인지 확인할 때는 parent 값을 직접 비교하기보다 find 결과를 비교해야 안전합니다.

// 권장하지 않는 방식
if (parent[a] == parent[b]) {
    // 같은 집합이라고 판단
}

// 올바른 방식
if (find(a) == find(b)) {
    // 같은 집합이라고 판단
}

같은 집합 비교는 반드시 find 결과로 확인하는 습관이 좋습니다.

18. 정리

이번 글에서는 유니온 파인드에 대해 정리했습니다.

유니온 파인드는 여러 원소를 집합으로 관리하는 자료구조이다.
union은 두 집합을 합치는 연산이다.
find는 어떤 원소가 속한 집합의 대표를 찾는 연산이다.
parent 배열을 이용해 각 원소의 부모를 저장한다.
두 원소가 같은 집합인지 확인할 때는 find 결과를 비교한다.
경로 압축을 사용하면 find 연산을 더 빠르게 만들 수 있다.
무방향 그래프에서 사이클 판별에 사용할 수 있다.
크루스칼 알고리즘에서도 유니온 파인드가 중요하게 사용된다.

유니온 파인드는 처음에는 parent 배열이 조금 낯설 수 있지만, 핵심은 단순합니다. 각 원소가 속한 대표를 찾고, 서로 다른 대표를 하나로 합치는 것입니다.

유니온 파인드의 핵심은 대표 원소를 기준으로 집합을 합치고, 같은 집합인지 빠르게 확인하는 것입니다.

다음 글 예고

다음 글부터는 탐색 알고리즘 영역으로 들어갑니다. 다음 글에서는 선형 탐색에 대해 알아보겠습니다.

배열이나 리스트를 처음부터 끝까지 확인하며 원하는 값을 찾는 가장 기본적인 탐색 방법을 예제로 정리해보겠습니다.

'Problem Solving > Algorithm' 카테고리의 다른 글

[알고리즘] 26. 이분 탐색 기초 (0)	2026.07.09
[알고리즘] 25. 선형 탐색(Linear Search) (0)	2026.07.09
[알고리즘] 23. 그래프 기초 (0)	2026.07.06
[알고리즘] 22. 트리 기초 (0)	2026.07.05
[알고리즘] 21. 힙(Heap) (0)	2026.07.04