본문 바로가기
카테고리 없음

유니온 파인드(Union-Find): 연결 요소를 빠르게 찾는 알고리즘

by xylavo 2025. 4. 12.

프로그래밍 세계에서 데이터 간의 연결 관계를 효율적으로 표현하고 관리하는 것은 매우 중요합니다. 유니온 파인드(Union-Find)는 이러한 연결 관계를 다루는 알고리즘 중 가장 우아하고 강력한 도구입니다.

어떤 문제를 해결하기 위함인가?

유니온 파인드 알고리즘은 기본적으로 '분리 집합(Disjoint Set)'이라고도 불리는 자료구조를 구현하는 방법입니다. 이 알고리즘은 다음과 같은 문제 상황에서 효과적인 해결책을 제공합니다:

  1. 그래프의 연결 요소 찾기: 어떤 노드들이 서로 연결되어 있는지 빠르게 판단해야 할 때, 유니온 파인드는 O(log n)에 판단할 수 있습니다. 대부분의 경우 이 정도의 시간복잡도로 해결이 가능하지만, 최적화를 거치면 O(α(n))이라는 거의 상수 시간에 가까운 속도로도 이를 처리할 수 있습니다. 여기서 α(n)은 아커만 함수의 역함수로, 실질적으로 대부분의 응용에서 4 이하의 매우 작은 값입니다.
  2. 동적인 그래프 관리: 노드 간의 연결이 계속해서 추가되는 동적인 환경에서도 유니온 파인드는 높은 효율성을 유지합니다. '유니온(Union)' 연산을 통해 두 집합을 합치고, '파인드(Find)' 연산으로 어떤 요소가 어떤 집합에 속하는지 빠르게 확인할 수 있습니다.
  3. 사이클 탐지: 무방향 그래프에 새 간선을 추가할 때, 해당 간선이 사이클을 형성하는지 쉽게 확인할 수 있습니다. 이는 크루스칼(Kruskal) 알고리즘과 같은 최소 신장 트리 알고리즘의 핵심 부분입니다.
  4. 네트워크 연결성 문제: 컴퓨터 네트워크에서 노드 간의 연결 여부를 추적하거나, 소셜 네트워크에서 사용자 그룹을 관리하는 등의 실제 응용 사례가 많습니다.

유니온 파인드의 가장 큰 장점은 이러한 복잡한 연결 관계를 매우 적은 메모리와 빠른 연산 시간으로 처리할 수 있다는 점입니다. 특히 경로 압축(Path Compression)과 랭크 기반 합치기(Union by Rank) 최적화를 적용하면, 대규모 데이터셋에서도 거의 선형에 가까운 성능을 보여주어 실무 환경에서 널리 활용되고 있습니다.

개념과 구현

유니온 파인드는 두 가지 핵심 연산으로 구성됩니다: '유니온(Union)'과 '파인드(Find)'입니다. 이름 그대로, 이 두 연산이 알고리즘의 근간을 이루고 있습니다.

기본 개념

  1. 파인드(Find): 특정 원소가 속한 집합의 대표 원소(루트)를 찾는 연산입니다. 이 연산을 통해 어떤 원소가 어떤 집합에 속해 있는지 확인할 수 있습니다.
  2. 유니온(Union): 두 개의 서로 다른 집합을 하나로 합치는 연산입니다. 두 집합의 루트를 찾아 한쪽을 다른 쪽의 부모로 설정함으로써 두 집합을 연결합니다.

구현

랭크 기반 합치기는 트리의 높이를 최소화하여 파인드 연산의 시간 복잡도를 O(log n)으로 유지하는 최적화 기법입니다. 각 노드마다 랭크(rank)라는 값을 유지하며, 이는 해당 노드를 루트로 하는 트리의 대략적인 높이를 나타냅니다.

랭크 기반 합치기를 사용하면 트리의 높이가 로그 수준으로 유지되어, 최악의 경우에도 find 연산은 O(log n)의 시간 복잡도를 가집니다. 이러한 최적화 없이 유니온 파인드를 구현하면 최악의 경우 연결 리스트와 유사한 형태의 트리가 만들어져 O(n)의 시간 복잡도를 가질 수 있습니다.

아래 구현에서는 경로 압축 최적화도 함께 사용하고 있는데, 이는 find 연산 중에 방문한 모든 노드의 부모를 루트로 직접 연결하는 방식입니다. 경로 압축만 적용해도 거의 상수 시간에 가까운 성능을 얻을 수 있지만, 랭크 기반 합치기와 함께 사용하면 더욱 일관된 성능을 보장할 수 있습니다.

다양한 응용: 코딩테스트 문제들

유니온 파인드 알고리즘은 다양한 코딩테스트 문제에서 강력한 도구로 활용됩니다. 실제 문제 유형과 해결 접근법을 살펴보겠습니다.

1. 섬 연결하기 문제

여러 개의 섬과 섬 사이를 잇는 다리 건설 비용이 주어졌을 때, 모든 섬을 연결하는 최소 비용을 구하는 문제입니다. 이는 전형적인 최소 신장 트리 문제로, 크루스칼 알고리즘과 유니온 파인드를 활용해 해결할 수 있습니다.

접근법: 모든 다리를 비용 순으로 정렬한 후, 가장 저렴한 다리부터 선택하되 이미 연결된 섬들은 제외합니다. 유니온 파인드로 섬들의 연결 상태를 효율적으로 관리합니다.

2. 친구 네트워크

온라인 서비스에서 사용자 A와 B가 친구 관계를 맺을 때, 두 사람이 속한 친구 네트워크의 크기를 구하는 문제입니다. 친구 네트워크란 직간접적으로 연결된 모든 사용자의 집합을 의미합니다.

접근법: 유니온 파인드의 기본 구조에 각 집합의 크기를 저장하는 배열을 추가하고, 유니온 연산에서 두 집합이 합쳐질 때 크기를 업데이트합니다.

3. 가장 큰 연결 요소 찾기

격자 형태의 맵에서 1은 땅, 0은 물을 나타낼 때, 가장 큰 땅(연결된 1의 집합)의 크기를 구하는 문제입니다.

접근법: 모든 땅(값이 1인 셀)을 노드로 간주하고, 인접한 땅끼리 유니온 연산을 수행합니다. 각 집합의 크기를 추적하면서 가장 큰 집합의 크기를 찾습니다.

4. 사이클 탐지 문제

무방향 그래프에서 사이클이 존재하는지 판별하는 문제입니다. 간선 정보가 순차적으로 주어질 때 어느 시점에서 사이클이 형성되는지 알아내야 합니다.

접근법: 각 간선을 처리할 때마다 양 끝점이 이미 같은 집합에 속해 있는지 확인합니다. 같은 집합에 속해 있다면 해당 간선은 사이클을 형성합니다.

5. 적의 적은 친구

N명의 사람이 있고, "A와 B는 적대 관계"라는 정보가 여러 개 주어질 때, 모든 사람을 두 그룹으로 나누어 각 그룹 내에 적대 관계가 없도록 할 수 있는지 판별하는 문제입니다.

접근법: 유니온 파인드를 약간 변형하여 "친구의 친구"와 "적의 적"을 관리합니다. 적대 관계인 두 사람 A와 B에 대해, A의 친구는 B의 적이 되고, B의 친구는 A의 적이 됩니다. 모순이 발생하면 두 그룹으로 나눌 수 없습니다.

 

유니온 파인드는 단순해 보이지만 놀라울 정도로 다양한 문제에 적용할 수 있는 강력한 알고리즘입니다. 특히 연결성과 그룹화가 관련된 코딩테스트 문제들을 효율적으로 해결할 수 있게 해 주며, 실제 개발 현장에서도 다양한 응용 가능성을 가진 필수적인 도구입니다.