[Python] 알고리즘 개념14 - 유니온 파인드(Disjoint Set)

 

 

🚀 1. 유니온 파인드(Disjoint Set)란?

유니온 파인드(Disjoint Set)는 여러 개의 집합을 관리하며, 두 원소가 같은 집합에 속해 있는지 확인하고, 서로 다른 집합을 합치는 연산을 수행하는 자료구조예요.

 

💡 쉽게 이해하기

• 🎭 서로 다른 팀(집합)이 있을 때, 두 팀이 같은 그룹인지 확인하고, 필요하면 하나로 합치는 과정을 자동으로 관리하는 구조예요.
• 🏢 회사 조직도에서 부서 간 연결 여부를 확인하거나, 친구 관계에서 같은 그룹에 속해 있는지를 판별할 때 사용돼요.
• 🏗 도로 네트워크에서 특정 도시들이 같은 네트워크로 연결되어 있는지 확인하는 문제에도 활용돼요.

 

➡ 유니온 파인드를 활용하면 빠르고 효율적으로 그룹 관계를 관리할 수 있어요!

**유니온 파인드(Disjoint Set)**는 서로소 집합(Disjoint Set)을 효율적으로 관리하는 자료구조예요.

 

💡 쉽게 이해하기

• 🎭 같은 그룹인지 확인하고, 서로 다른 그룹을 합치는 연산을 수행하는 알고리즘이에요!
• 🏢 네트워크 연결, 친구 관계 탐색, 최소 신장 트리(MST) 알고리즘에서 자주 사용돼요.

 

📌 유니온 파인드에서 사용하는 두 가지 핵심 연산

1. Find(찾기 연산) → 특정 원소가 속한 집합의 대표 노드를 찾는 연산
2. Union(합치기 연산) → 두 개의 집합을 하나로 합치는 연산

➡ 이 두 연산을 활용해, 집합을 관리할 수 있어요!

---

 

 

🚀 2. 기본 유니온 파인드 구현

 

📌 유니온 파인드의 핵심 연산

1. Find(찾기 연산): 특정 원소가 속한 집합의 대표 노드를 찾는 연산
2. Union(합치기 연산): 두 개의 집합을 하나로 합치는 연산

 

💡 비유를 통해 쉽게 이해하기

• 🏀 농구 리그에서 팀을 관리한다고 가정해볼게요. 처음에는 각 선수들이 독립적인 팀을 가졌지만, 경기에서 승리하면 두 팀이 합쳐지는 시스템이 있다고 해요. 이 과정에서 두 선수가 같은 팀에 있는지 확인하는 것이 Find 연산, 두 팀을 합치는 것이 Union 연산이에요.

➡ 이제 기본적인 코드 구현을 보면서 이해해볼까요?

 

💡 배열을 이용한 유니온 파인드 기본 구현

# 유니온 파인드 기본 구현
class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]  # 자기 자신을 부모로 설정

    def find(self, x):
        if self.parent[x] == x:
            return x
        return self.find(self.parent[x])  # 재귀적으로 부모 찾기

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a  # b의 대표 노드를 a로 설정

# 사용 예시
dsu = DisjointSet(6)
dsu.union(1, 2)
dsu.union(2, 3)
print(dsu.find(3))  # 출력: 1 (1, 2, 3이 같은 집합)

➡ 각 노드의 부모를 저장하여 집합을 관리해요!

---

 

 

🚀 3. 경로 압축(Path Compression) 최적화

경로 압축 기법을 사용하면 Find 연산의 속도를 획기적으로 줄일 수 있어요!

 

📌 경로 압축의 핵심 원리

• 일반적으로 Find 연산을 수행할 때, 부모 노드를 하나씩 따라가면서 최상위 부모(루트)를 찾게 돼요.
• 하지만 경로 압축을 적용하면, 중간 과정에서 만난 모든 노드들을 루트 노드에 직접 연결하여 탐색 속도를 O(1)에 가깝게 만들 수 있어요!

 

💡 비유를 통해 쉽게 이해하기

• 🏡 마을 지도 찾기를 생각해보세요! 예전에는 마을 주민이 가게 위치를 물을 때, 한 명씩 거쳐 가면서 물어야 했어요. 하지만 이제부터는 마을 촌장이 모든 위치를 한눈에 볼 수 있는 큰 지도를 만들어둔다면? 주민들은 즉시 가게 위치를 확인할 수 있겠죠? 🗺️

 

➡ 이제 코드에서 어떻게 적용되는지 확인해볼까요?

유니온 파인드에서 Find 연산을 최적화하면 탐색 속도를 더욱 빠르게 만들 수 있어요!

 

📌 경로 압축(Path Compression)이란?

• 🚀 Find 연산을 수행할 때, 경로를 따라 부모를 갱신하여 탐색 시간을 단축하는 기법이에요.
• ⚡ 이 방법을 사용하면, 모든 원소의 부모가 루트 노드를 직접 가리키게 되어 탐색이 O(1)에 가까워져요!

 

💡 경로 압축 적용 코드

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축 적용
        return self.parent[x]

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a

➡ 경로 압축을 활용하면, 트리의 높이를 줄여 탐색 속도를 개선할 수 있어요!

---

 

 

🚀 4. 유니온 연산 최적화 (랭크 기반 합치기)

 

📌 유니온 연산을 최적화하기 위해 랭크(Rank) 개념을 활용할 수 있어요!

• 🔢 각 집합의 크기(또는 깊이)를 고려하여 작은 집합을 큰 집합에 병합
• 🚀 균형 잡힌 트리 구조를 유지하여 탐색 속도를 개선

 

💡 랭크 기반 유니온 구현

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size  # 트리 높이(랭크) 저장

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축 적용
        return self.parent[x]

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            if self.rank[root_a] > self.rank[root_b]:
                self.parent[root_b] = root_a
            else:
                self.parent[root_a] = root_b
                if self.rank[root_a] == self.rank[root_b]:
                    self.rank[root_b] += 1

➡ 랭크 정보를 활용하면 트리의 균형을 유지할 수 있어요!

---

 

 

🚀 5. 유니온 파인드의 시간복잡도

 

📌 Find와 Union 연산의 성능 비교

• 기본적인 유니온 파인드는 O(n) 시간이 걸릴 수 있어요.
• 하지만 경로 압축과 랭크 기반 합치기 기법을 사용하면 거의 O(1) 수준으로 개선 가능해요!

 

💡 실생활 예제

• 🎓 학교 친구 찾기: 같은 반에 있는 친구인지 확인하는 과정
• 🏙️ 도시 연결망 확인: 특정 두 도시가 도로망으로 연결되어 있는지 확인하는 문제

➡ 이제 유니온 파인드를 사용하면 어떻게 효율적으로 데이터를 관리할 수 있는지 확실히 이해할 수 있어요!

 

 

연산 종류 / 기본 구현 / 시간복잡도 경로 압축 + 랭크 사용 시

Find(찾기)	O(n)	O(α(n)) (거의 O(1))
Union(합치기)	O(n)	O(α(n)) (거의 O(1))

📌 여기서 α(n)는 거의 O(1) 수준의 매우 작은 함수(아커만 역함수)예요! ➡ 즉, 유니온 파인드는 최적화하면 거의 O(1) 속도로 동작할 수 있어요!

---

 

 

🚀 6. 유니온 파인드의 활용 예시

 

📌 유니온 파인드는 어디에서 사용될까요?

1. 네트워크 연결 문제 → 같은 네트워크에 속해 있는지 확인
2. 친구 관계 탐색 (SNS 추천 알고리즘) → 서로 연결된 사람들 찾기
3. 최소 신장 트리(MST) 알고리즘 (크루스칼 알고리즘) → 그래프의 최소 비용 연결
4. 컴퓨터 클러스터링 → 여러 개의 서버가 연결되어 있는지 판단
5. 도시 경로 연결 문제 → 도로가 연결되어 있는지 확인

➡ 유니온 파인드는 코딩테스트에서 자주 등장하는 핵심 개념이에요! 😊

---

 

 

✅ 마무리 정리

• 유니온 파인드는 서로소 집합을 관리하는 알고리즘이에요.
• Find 연산을 최적화하는 경로 압축(Path Compression)을 사용하면 탐색이 빨라져요!
• Union 연산을 최적화하는 랭크 기반 합치기(Rank-Based Union)를 활용하면 트리 균형을 유지할 수 있어요.
• 최적화된 유니온 파인드는 거의 O(1) 속도로 동작하므로 매우 효율적이에요!