# Processing of Disjoint Sets using Union-Find Algorithms (9th weeks)

**Contents**

---

**1️⃣** 유니온 파인드의 개요 (Overview of Union Find)  
**2️⃣** 연결 리스트 구현 (Implementation of Linked List)  
**3️⃣** 트리 구현 (Implementation of Tree)  
**4️⃣** 파이썬의 1차원 리스트 구현 (Implementation of 1-Dimensional List in Python)

---

### Summary

### **유니온 파인드 개요 (Overview of Union FInd)**

* **유니온 파인드**는 집합 간의 연결과 대표 노드 탐색을 빠르게 수행하기 위한 알고리즘이다.
    
* **응용 분야**: 네트워크 연결, 그룹화 문제, 상호 배타적 집합 관리 등에서 활용된다.
    

### **주요 연산(Basic Operation)**

☑️ `Make_Set(x)` 원소 `x`가 독립된 집합을 생성하도록 한다.

☑️ `Find_Set(x)` 원소 `x`가 속한 집합의 대표 노드를 반환한다.

☑️ `Union(x, y)` 원소 `x`와 `y`가 속한 두 집합을 하나로 합친다.

### **구현 방식(Implementation)**

☑️ **연결 리스트 (Linked List)**

* 각 노드가 자신의 다음 노드를 가리키며 연결되는 방식이다.
    
* Union 연산 시 대표 노드를 변경하는 과정에서 많은 연산이 필요할 수 있다.
    

☑️ **트리 (Tree)**

* 트리 구조를 사용하여 각 집합의 대표 노드를 트리의 루트로 설정하는 방식이다.
    
* 경로 압축(Path Compression)과 랭크(Rank)를 사용해 탐색 및 결합을 최적화한다.
    

☑️ **1차원 리스트 (1-Dimensional Array)**

* 인덱스를 사용하여 각 노드의 부모 정보를 저장한다.
    
* 빠르고 직관적인 접근 방식으로, 배열을 통해 간편하게 관리할 수 있다.
    

### 최적화 기법(Optimization Methods)

☑️**경로 압축 (Path Compression)**: Find 연산 시 트리의 깊이를 줄여 탐색 속도를 개선한다.

☑️**랭크 기반 유니온 (Union by Rank)**: 트리의 균형을 유지하여 트리의 높이를 최소화한다.

---

### 상호 배타적 집합이란? (What is Disjoin Sets)?

  
**상호 배타적 집합**(Disjoint Sets)은 서로 겹치는 원소가 없는 집합들을 의미한다. 즉, **각 원소는 하나의 집합에만 속할 수 있고, 다른 집합과는 공유되지 않는** 구조이다.

유니온 파인드 알고리즘에서 이 개념이 중요한 이유는, 특정 원소가 어느 집합에 속하는지를 효율적으로 관리하고, 두 집합을 합칠 때 겹치지 않도록 하기 위함이다.  

---

### 상호 배타적 집합의 예시 (Example of Disjoint Sets)

**<mark>💡요약: </mark> 그래프의 연결 성분** (**Connected Components of a Graph**)은 서로 연결된 노드들의 집합이다. 각 성분은 독립적으로 존재하며, 다른 성분과 연결되어 있지 않다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730948208546/0da88c82-6171-4bcd-b4c0-5372a32a4848.png align="center")

그래프에서 연결 성분은 서로 연결된 노드(점)들의 그룹을 의미하며, 이들 사이에는 경로가 존재한다. 연결되지 않은 다른 성분들과는 어떠한 연결도 이루어져 있지 않아서, 하나의 독립적인 **서브그래프** (**Subgraph**)로 볼 수 있다.

이미지에는 총 세 개의 독립적인 그래프 성분이 회색 배경으로 나뉘어 표현되어 있다. 각 성분은 다음과 같은 형태를 띄고 있다.

1. 첫 번째 성분: 상단에 하나의 중심 노드가 있고, 그 아래 두 개의 노드가 연결된 형태로 이루어져 있다.
    
2. 두 번째 성분: 네 개의 노드가 있으며, 이 노드들은 다양한 방식으로 서로 연결되어 있다.
    
3. 세 번째 성분: 두 개의 노드가 단순하게 한 줄로 연결된 형태를 보여주고 있다.
    

---

## **1️⃣** 유니온 파인드의 개요  
(Overview of Union Find)  

### 유니온 파인드의 개념 (Concept of Union Find)

**<mark>💡요약: </mark>** 유니온 파인드는 그래프에서 **상호 배타적 집합** (**Disjoint Sets**)을 효율적으로 처리하기 위해 고안된 자료구조로, 기본 연산으로는 **Make\_Set** (**Create a Set**), **Find\_Set** (**Find the Set**), **Union** (**Combine Sets**)이 있으며, 이를 통해 연결된 그래프 구조를 형성한다.  

* **유니온 파인드의 개념** (**Concept of Union-Find**):  
    유니온 파인드는 상호 배타적인 집합을 다루며, 각 집합의 연관성과 포함 관계를 효율적으로 관리할 수 있도록 돕는다.
    
* **유니온 파인드의 기본적인 연산** (**Basic Operations of Union-Find**):  
    유니온 파인드 자료구조에서 사용하는 주요 연산은 다음과 같다.
    
    * **Make\_Set(x)**: 원소 x로만 구성된 새로운 집합을 생성한다.
        
    * **Find\_Set(x)**: 원소 x가 포함된 집합을 찾는다.
        
    * **Union(x, y)**: 원소 x가 포함된 집합과 y가 포함된 집합을 합친다.
        

---

### 유니온 파인드의 구현 방식(**Implementation of Union-Find**)

**<mark>💡요약: </mark>** 유니온 파인드의 대표적인 3가지 구현 방식으로는 **연결 리스트** (**Linked List**), **트리** (**Tree**), 그리고 **1차원 리스트(배열)** (**1D Array**)가 있다. 이 중에서 **대표 노드** (**Representative Node**)를 이용해서 각 집합을 구분하는데, 대표 노드는 해당 집합의 주요 원소로, 각 원소가 어느 집합에 속하는지를 나타내는 기준이 된다. 각 구현 방식은 대표 노드를 찾거나 지정하는 방식이 다르다.

  
☑️ **연결 리스트 구현** (**Linked List Implementation**):  
**포인터**를 이용하여 대표 노드를 지정한다. 각 원소가 리스트 형태로 연결되어 있으며, 리스트의 첫 번째 원소가 대표 노드가 된다.

☑️ **트리 구현** (**Tree Implementation**):  
**트리 구조**를 활용하여 각 집합의 대표 노드를 찾아간다. 트리의 루트 노드가 대표 노드가 되며, 효율적인 연산을 위해 경로 압축(path compression)과 같은 기법을 사용한다.

☑️ **1차원 리스트(배열) 구현** (**1D Array Implementation**):  
**각 원소**가 리스트의 값으로 대표 노드를 가리킨다. **배열의 인덱스**를 원소로 보고, 그 인덱스에 해당하는 값이 해당 집합의 대표 노드이다.

---

## **2️⃣** 연결 리스트 구현  
(Implementation of Linked List)

### 유니온 파인드의 구현 방식 #1 - **연결 리스트의 노드 구조** (**Implementation of Union-Find** 1# - **Node Structure in a Linked List**)

**<mark>💡요약:</mark>** 연결 리스트는 각 **노드** (**Node**)가 서로 연결되어 있는 자료구조로, 각 노드는 **대표 노드 포인터** (**Pointer to Representative Node**), **필드 값** (**Field Value**), **다음 노드 포인터** (**Pointer to Next Node**)로 구성된다. 이를 통해 각 노드는 자신이 속한 집합의 대표 노드를 가리키며, 리스트 형태로 연결되어 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730955877319/f066a6c2-2c73-4b6e-a694-fa5a750f68de.png align="center")

* **대표 노드 포인터** (**Pointer to the Representative Node**):  
    각 노드에는 해당 노드가 속한 집합의 대표 노드를 가리키는 포인터가 있다. 예를 들어, 노드 b는 노드 a를 대표 노드로 가리키고 있다.
    
* **필드 값** (**Field Value**):  
    노드는 데이터를 저장하는 필드를 가지고 있다. 여기서는 각 노드가 a와 b로 표현되어 있다.
    
* **다음 노드 포인터** (**Pointer to the Next Node**):  
    각 노드는 리스트 내에서 다음 노드를 가리키는 포인터를 포함하고 있다. 이를 통해 리스트가 연결된 구조를 유지할 수 있게된다.
    

---

### **연결리스트에서 사용되는 유니온 파인드의 기본적인 연산** (**Basic Operations of Union Find from Linked List**): `Make_Set(x)` & `Find_Set(x)`

**<mark>💡요약: </mark> Make\_Set(x)**는 새로운 집합을 생성하고, **Find\_Set(x)**는 해당 집합의 **대표 노드** (**Representative Node**)를 반환하는 역할을 한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730960121733/105b0c25-7391-4ddc-a60a-14c834b6c568.png align="center")

**Make\_Set(x)의 구현** (**Implementation of Make\_Set(x)**):

* **Make\_Set(x)** 연산은 원소 x로만 구성된 새로운 집합을 생성한다. 이는 x를 하나의 독립적인 집합으로 만들어, 다른 집합과 분리된 상태로 유지하게 한다.
    
* 예시에서 x는 하나의 노드로서 자신을 대표하고 있다. 이때, x는 집합의 꼬리(tail)로도 표시된다.
    

**Find\_Set(x)의 구현** (**Implementation of Find\_Set(x)**):

* **Find\_Set(x)** 연산은 주어진 노드 x가 속한 집합의 대표 노드를 반환한다. 이 연산을 통해 x가 어느 집합에 속해 있는지를 알 수 있다.
    
* 이 예시에서는 x가 이미 대표 노드이므로, **Find\_Set(x)** 연산의 결과는 x자신이 된다.
    

**💡예시**

* **Make\_Set(5)**를 수행하면 `{5}`라는 집합이 생성되고, `5`가 이 집합의 대표 노드이자 꼬리(`tail`)가 된다.
    
* **Make\_Set(5)**를 먼저 수행한 후 **Find\_Set(5)**를 실행하면, `5`가 집합의 유일한 원소이므로 `5`가 대표 노드로 반환되게 된다.
    

---

### **연결리스트에서 사용되는 유니온 파인드의 기본적인 연산** (**Basic Operations of Union Find from Linked List**): `Union(x, y)`

**<mark>💡요약: </mark> Union 연산**은 두 개의 집합을 하나로 합치는 과정으로, 이를 통해 상호 배타적 집합을 통합할 수 있게 하여 하나의 대표 노드를 공하는 집합으로 만든다.

* **x, y의 대표 노드 찾기** (**Finding Representative Nodes of x and y**):
    
    * 첫 번째 단계에서는 **Find\_Set(x)**와 **Find\_Set(y)**를 수행하여 각각 x와 y의 **대표 노드** (**Representative Node**)를 찾는다. 이는 각각의 집합이 시작되는 노드를 의미한다.
        
* **tail 노드 변경** (**Changing the Tail Node**):
    
    * 두 번째 단계에서는 **부집합** (**Smaller Set**)의 대표 노드를 **주집합** (**Larger Set**)의 **tail 노드** (**Tail Node**)로 설정하여 연결한다. 이는 두 집합을 하나로 합치기 위한 준비 과정이다.
        
* **대표 노드 변경** (**Changing the Representative Node**):
    
    * 마지막 단계에서는 부집합의 모든 원소들이 주집합의 대표 노드를 가리키도록 **대표 노드를 변경**한다. 이를 통해 두 집합이 하나의 집합으로 합쳐지며, 모든 원소는 주집합의 대표 노드를 공유하게 된다.
        

  
💡**예시:** 두 개의 집합 A와 B가 있다고 가정해 보자

* 집합 A: {1, 2, 3} (대표 노드: 1)
    
* 집합 B: {4, 5} (대표 노드: 4)
    

여기서 Union(1, 4)를 수행한다고 가정하면 다음과 같은 단계가 진행된다.

1. **대표 노드 찾기 (Find\_Set)**: 각각의 대표 노드인 1과 4를 찾는다.
    
2. **tail 노드 연결**: 두 집합의 크기를 비교하여 작은 집합의 대표 노드를 큰 집합의 tail에 연결한다. 여기서 B가 더 작기 때문에, B의 대표 노드 4를 A의 tail (3)에 연결한다.
    
3. **대표 노드 설정**: B의 모든 원소가 A의 대표 노드인 1을 가리키도록 변경한다.
    

결과적으로, A와 B는 {1, 2, 3, 4, 5}로 합쳐지며, 모든 원소가 대표 노드 1을 공유하게 된다.

---

### `Union(x, y)` 추가설명: 두 개의 **집합** (**Sets**)을 하나로 **합치는 과정** (**Union Process**)

**<mark>💡요약</mark>**<mark>:</mark> 두 집합을 **부집합** (**Smaller Set**)을 **주집합** (**Larger Set**)으로 나누어, 더 작은 부집합을 큰 주집합에 연결하는 방식으로 합치게 된다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730960441592/a8bc54bc-6c2b-42bc-8ffe-360b1582a779.png align="center")

☑️**부집합** (**Subordinate Set**):

* 부집합은 노드 a, b, c로 구성되어 있으며, 마지막 노드 c가 **tail 노드** (**Tail Node**)로 표시된다. 이 집합은 주집합에 합쳐질 예정이다.
    

☑️ **주집합** (**Main Set**):

* 주집합은 노드 d, e, f, g, h로 구성되어 있으며, 마지막 노드 h가 **tail 노드**로 표시된다. 이 주집합에 부집합을 연결함으로써 전체 집합이 하나로 합쳐지게 된다.
    

☑️ **합치는 과정** (**Union Process**):

* 먼저, 부집합의 **tail 노드**인 c를 주집합의 **tail 노드**인 h에 연결합니다.
    
* 그 결과, 부집합의 모든 원소는 주집합의 **대표 노드** (**Representative Node**)인 d를 공유하게 된다. 이로써 두 집합이 하나의 큰 집합으로 합쳐지게 되었다.
    

---

### `Union(x, y)` 추가설명: **대표 노드** (**Representative Node**)와 **tail 포인터** (**Tail Pointer**)를 변경하는 과정

**<mark>💡요약</mark>**<mark>: </mark> 중요한 점은 포인터 갱신 작업을 최소화하기 위해 **큰 집합**을 주집합으로, **작은 집합**을 부집합으로 삼아 합치는 것이다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730960608833/62a30c0f-af85-495b-a0a2-2bf7b0a256d4.png align="center")

☑️**대표 노드를 변경** (**Change Representative Node**):

* 두 집합이 합쳐질 때, 작은 집합의 모든 노드가 큰 집합의 **대표 노드**를 가리키도록 변경한다. 이렇게 하면 모든 노드가 동일한 대표 노드를 가지게 되어 하나의 집합으로 인식된다.
    

☑️ **tail 포인터 변경** (**Change Tail Pointer**):

* 큰 집합의 마지막 노드(tail)를 작은 집합의 첫 번째 노드와 연결하여 두 집합을 하나의 연속된 리스트로 만든다. 이 과정에서 작은 집합의 tail 포인터가 전체 합쳐진 집합의 마지막 노드를 가리키도록 설정된다.
    

☑️ **최적화 포인트** (**Key Point**):

* 대표 노드를 가리키는 포인터를 갱신하는 작업을 최소화하기 위해, 항상 더 큰 집합을 주집합으로 삼고 작은 집합을 부집합으로 설정하여 합치게 된다. 이렇게 하면 포인터 변경 횟수가 줄어들어 효율성이 높아진다.
    

---

### **각 연산의 수행 시간** (**Execution Time of Operations in Linked List Union-Find**)

**<mark>💡요약: </mark>** `Make_Set(x)`와 `Find_Set(x)`는 각각 O(1)의 **상수 시간** (**Constant Time**)이 소요되며, **Union(x, y)**는 포인터 갱신 작업으로 인해 **O(n \\log n)**의 수행 시간이 걸린다. 유니온 파인드 자료구조가 왜 집합 연산을 빠르고 효율적으로 처리할 수 있는 이유를 소개한다.  

* `Make_Set(x)`: O(1)
    
    * 새로운 집합을 만드는 **Make\_Set(x)** 연산은 **상수 시간** (**Constant Time**), 즉 O(1)의 시간이 소요된다. 이는 항상 일정한 시간 안에 수행다.
        
* `Find_Set(x)` : O(1)
    
    * 특정 원소가 속한 집합의 **대표 노드**를 찾는 **Find\_Set(x)** 연산 역시 **상수 시간** O(1)이 걸린다.
        
* **Union(x, y)**: 대표 노드를 갱신하는 작업이 전체 시간 결정
    
    * 두 집합을 합치는 **Union(x, y)** 연산에서는 **대표 노드**를 갱신해야 하는 작업이 포함되며, 이는 전체 수행 시간에 영향을 미치게 된다. 특히, 매번 작은 집합이 큰 집합에 합쳐지면서 대표 노드를 가리키는 **포인터 갱신**이 최소화된다.
        
    * 작은 집합이 합쳐지면서 **집합의 크기**는 1 → 2 → 2² → 2³ → … 식으로 늘어나게 된다. 이 과정에서 최대 **갱신 횟수**는 **log\_2 ​n** 만큼 반복되며, 모든 원소에 대해 계산하면 포인터 갱신 계산으로 인해 O(n log n) 이 된다.
        

---

### **각 연산들의 수행 시간 예**  
(Example of **Execution Time of Union-Find**)

**<mark>💡요약:</mark>** **Make\_Set**, **Union**, **Find\_Set** 연산들이 주어진 입력 크기에서 얼마나 빠르게 동작하는지에 대한 시간 복잡도를 설명하고 있다.

* **총 수행 시간 계산**
    
    * 유니온 파인드의 연산이 m번 일어나고, 새로운 집합을 만드는 **Make\_Set**이 n번 발생할 때, 전체 수행 시간은 **O ( m + n log ⁡n)**이다.
        
* **각 연산의 시간 복잡도**
    
    * **Make\_Set**과 **Find\_Set**은 각각 최대 **O(m)**시간이 소요된다.
        
    * **Union** 연산은 **O (n log⁡2 n)** 시간이 걸린다.
        

**<mark>💡예시:</mark>** 노드들이 서로 다른 집합에 포함되어 있다고 가정하고, 다음과 같은 연산을 수행한다고 가정 하자

1. **Make\_Set 연산**:
    
    * 노드 1, 2, 3, 4를 각각 독립된 집합으로 초기화한다.
        
    * 이 경우, Make\_Set은 각 노드마다 𝑂(1)의 시간이 걸리므로 4개의 노드를 초기화하는 데 𝑂(4) 시간이 소요된다.
        
2. **Union 연산**:
    
    * 노드 1과 노드 2를 Union 연산으로 하나의 집합으로 합친다.
        
    * 이어서 노드 3과 노드 4를 Union으로 합친다.
        
    * 마지막으로 노드 1과 노드 3의 집합을 합친다.
        
    * 각 Union 연산은 연결 리스트의 끝에 노드를 추가하는 방식으로, 최악의 경우 𝑂(log n)의 시간이 걸리므로 총 𝑂(3 log n) 시간이 소요되었다.
        
3. **Find\_Set 연산**:
    
    * 최종적으로 노드 4가 속한 집합의 대표 노드를 찾는다. Find\_Set은 대표 노드를 찾을 때 연결 리스트를 따라가야 하므로, 연결 리스트의 길이에 비례하여 시간이 걸립니다. 최악의 경우 𝑂(log n)의 시간이 필요하다.
        
    * 이 예제에서는 Make\_Set 연산이 𝑂(4)이고, Union과 Find\_Set 연산이 합쳐서 𝑂(3 log n) 시간이 걸린다. 따라서, 전체 수행 시간은 유니온 파인드의 시간 복잡도인 𝑂(m + n log n)에 근사하다.
        

---

## **3️⃣** 트리 구현 (Implementation of Tree)

##   
유니온 파인드의 구현 방식 #2 - **트리 구조** (**Implementation of Union-Find** 2# - **Tree Structure**)

**<mark>💡요약: </mark>** 유니온 파인드에서 **트리 구조**는 같은 집합의 원소들을 하나의 **대표 원소**로 관리하기 위해 사용된다. 각 원소는 **부모 노드**를 가리키며, 최상단 **루트 노드**가 전체 집합의 대표가 된다.  

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730961975964/4d9199a5-f960-4f88-a032-87a1e4604dc6.png align="center")

☑️ **트리 구조와 대표 원소**

* 모든 원소는 하나의 트리로 연결되며, 트리의 최상단에 있는 **루트 노드**가 집합의 대표 원소가 된다. 예를 들어, 트리의 루트 노드인 c가 전체 집합의 대표 원소다 된다.
    

☑️**부모 노드를 가리킴**

* 일반적인 트리 구조와 다르게, **유니온 파인드 트리**에서는 자식 노드가 자신의 부모 노드를 가리킨다. 예를 들어, a는 b를, b는 c를 가리키고 있다.
    

☑️ **대표 원소로 집합 관리**

* 트리의 루트를 통해 해당 집합의 모든 원소가 어떤 집합에 속해 있는지 쉽게 확인할 수 있다.
    

---

### **트리구조에서 사용되는 유니온 파인드의 기본적인 연산** (**Basic Operations of Union Find from Tree Structure**):

### `Make_Set(x)`

**<mark>💡요약:</mark>** **Make\_Set(x)**는 원소 x를 유일한 원소로 가지는 집합을 생성하고, x의 부모 포인터를 자기 자신으로 설정하여 **루트**와 **대표 원소**가 되도록 한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730963075479/9b39a08e-713c-4253-9bae-51eb6e956edf.png align="center")

* **원소 x로 집합 생성**
    
    * **Make\_Set(x)**는 원소 x를 유일한 원소로 가지는 집합을 생성한다. 이 집합은 하나의 트리로 구성되며, 루트 노드는 x가 된다.
        
* **부모 포인터가 자기 자신을 가리킴**
    
    * 초기화된 노드 x의 **부모 포인터** (**Parent Pointer**)는 자기 자신을 가리키도록 설정된다. 이는 트리에서 x가 그 자체로 독립적이라는 것을 의미한다.
        
* **트리의 루트가 대표 원소**
    
    * 트리의 루트인 x는 집합의 **대표 원소** (**Representative Element**) 역할을 한다. x가 포함된 집합의 대표가 x 자신이라는 뜻이다.
        

---

### **트리구조에서 사용되는 유니온 파인드의 기본적인 연산** (**Basic Operations of Union Find from Tree Structure**):

### `Find_Set(x)`

**<mark>💡요약: </mark> Find\_Set(x)** 연산은 노드 x에서 시작해 **부모 노드**를 따라가며 **루트 노드**에 도달할 때까지 이동하며, 루트 노드를 **대표 원소**로 반환한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1730963257188/e33d7faa-8ef0-4514-8a9c-a9db58620d81.png align="center")

☑️**부모 노드를 따라가기**

* **Find\_Set(x)**는 원소 x의 **부모 노드** (**Parent Node**)를 따라간다. 부모 노드의 포인터를 반복적으로 따라가면서 루트에 도달할 때까지 계속 이동한다.
    

☑️**루트 노드까지 이동**

* 부모 노드를 계속해서 따라가다 보면, 언젠가 **자기 자신을 가리키는 노드**(루트 노드)에 도달하게 된다. 이 루트 노드가 해당 집합의 대표 원소이다. 예를 들어, 노드 x에서 출발하여 e, h를 거쳐 **대표 노드** c에 도달한다.
    

☑️ **대표 원소 반환**

* 최종적으로 루트 노드에 도달하면 그 노드를 대표 원소로 반환한다. 루트 노드 c는 노드 x가 속한 집합의 대표 원소이다.
    

**<mark>💡예제:</mark>** 여러 팀이 하나의 리더 아래 그룹으로 묶여 있다고 가정해보자. x가 어떤 팀의 일원인지 알고 싶다면 x의 리더(대표 원소)를 찾아가면서 리더를 찾을 때까지 상위 계층을 따라가면 된다.

---

### **트리구조에서 사용되는 유니온 파인드의 기본적인 연산** (**Basic Operations of Union Find from Tree Structure**):

### `Union(x, y)`

**<mark>💡요약: </mark> Union(x, y)** 연산은 두 개의 집합을 하나로 합쳐서 **대표 노드**를 공유하도록 만들어 구현한다. 이때, 한 집합의 **대표 노드**가 다른 집합의 대표 노드를 가리키게 하여 연결하는 방식이다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731026032419/ea65c1ae-03d2-4b57-82e3-612a11728425.png align="center")

* **두 집합 합치기**
    
    * 왼쪽에는 대표 노드가 c인 집합이 있고, 오른쪽에는 대표 노드가 e인 집합이 있다. 이 두 집합을 **Union(x, y)** 연산을 통해 하나로 합치려고 한다.
        
* **대표 노드 연결**
    
    * 두 집합을 하나로 합치기 위해 **대표 노드** 중 하나가 다른 집합의 대표 노드를 가리키도록 설정한다. 예시에서는 노드 e가 노드 c를 가리키도록 부모 포인터를 변경하여 하나의 트리로 연결한다.
        
* **합쳐진 결과**
    
    * 결과적으로, e를 포함한 오른쪽 집합이 c를 대표 노드로 가지는 왼쪽 집합에 연결되어 하나의 큰 집합이 된다. 이제 모든 노드는 루트 노드 c를 통해 같은 집합에 속하게 된다.
        

**<mark>💡예제: </mark>** 대규모 네트워크에서 **연결 상태 확인을 빠르게 수행**해야 할 때 특히 유용한 방법이 될 수 있다. 서버 A, B, C, D가 있다고 가정해보자

1. **초기 상태**: 각 서버는 독립적인 네트워크로 초기화된다.
    
    * `Make_Set(A)`, `Make_Set(B)`, `Make_Set(C)`, `Make_Set(D)`
        
2. **연결 추가**: 네트워크 관리자가 서버 A와 B를 연결하면 `Union(A, B)` 연산을 수행한다. 이제 A와 B는 하나의 네트워크로 간주된다.
    
3. **추가 연결**: 서버 C와 D를 연결하려면 `Union(C, D)`를 수행한다. 이로써 C와 D는 하나의 네트워크에 속하게 된다.
    
4. **네트워크 통합**: 나중에 A와 C가 연결되면 `Union(A, C)`를 통해 A, B, C, D가 하나의 네트워크로 합쳐진다.
    
5. **연결 여부 확인**: 예를 들어, 서버 B와 D가 같은 네트워크에 속해 있는지 확인하려면 **Find\_Set(B)**와 **Find\_Set(D)**를 호출해 같은 대표 노드를 가지고 있는지 비교하면 된다.
    

---

### **트리구조에서 사용되는 유니온 파인드의 의사 코**드 (**Pseudocode for Tree Implementation of Union-Find**)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731026613141/d479733a-3afd-4a6e-a272-aac4b529cb38.png align="center")

**<mark>💡요약: </mark>** `Make_Set(x)`는 노드 x를 독립적인 집합으로 초기화하고, `Union(x, y)`는 두 집합을 하나로 합치며, `Find_Set(x)`는 노드 x의 대표 노드를 찾는다.

* `Make_Set(x)`
    
    * **Make\_Set(x)** 연산은 새로운 집합을 만들기 위해, 노드 x를 유일한 원소로 가지는 집합으로 초기화한다.
        
    * **x.parent ← x**로 설정하여, 노드 x가 자기 자신을 부모로 가리키도록 한다. 즉, 노드 x는 자신의 **대표 노드** (**Representative Node**)가 되는 것이다.
        
* `Union(x, y)`
    
    * **Union(x, y)** 연산은 두 집합을 하나로 합치는 기능을 수행한다.
        
    * **Find\_Set(y).parent ← Find\_Set(x)**를 통해, y가 속한 집합의 대표 노드가 x의 대표 노드를 가리키도록 연결된다. 이로써 두 집합은 하나로 합쳐진다.
        
* `Find_Set(x)`
    
    * **Find\_Set(x)** 연산은 노드 x가 속한 집합의 대표 노드를 찾는 기능을 한다.
        
    * **if (x = x.parent) return x**: 만약 x가 자기 자신을 부모로 가리킨다면, x는 루트 노드이므로 x를 반환한다.
        
    * **else return Find\_Set(x.parent)**: 그렇지 않다면, x의 부모 노드로 이동하여 다시 **Find\_Set**을 재귀적으로 호출하여 루트 노드에 도달할 때까지 반복한다.
        

**<mark>💡예제: </mark> 파일 시스템 관리**라는 상황을 예로 들어보자. 대형 파일 시스템에서 여러 디렉토리(폴더)들이 있고, 이들 사이에 병합 작업이 필요할 때가 있다. 예를 들어, 두 디렉토리를 하나로 합치거나 특정 파일이 어느 디렉토리에 속해 있는지 빠르게 찾아야 할 때가 있다. 유니온 파인드의 연산을 사용하면 이러한 파일 및 디렉토리 관계를 효율적으로 관리할 수 있게된다.

#### 연산 적용

1. **Make\_Set(x)**: 새 디렉토리 또는 파일을 시스템에 추가할 때 **Make\_Set**을 통해 각각 독립적인 디렉토리로 초기화한다.
    
    * 예를 들어, 디렉토리 "Dir1"과 "Dir2"가 있다고 하면, `Make_Set(Dir1)`과 `Make_Set(Dir2)`를 호출하여 각 디렉토리가 독립적인 집합(루트)을 갖도록 설정한다.
        
2. **Union(x, y)**: 두 디렉토리를 하나로 병합할 때 사용한다.
    
    * 예를 들어, "Dir1"과 "Dir2"를 병합하려면 `Union(Dir1, Dir2)`를 호출하여 하나의 루트를 공유하도록 만든다.
        
    * 이렇게 하면 "Dir1"과 "Dir2"가 하나의 디렉토리 구조로 연결되며, 하위 파일도 함께 포함된 집합으로 관리된다.
        
3. **Find\_Set(x)**: 특정 파일이나 디렉토리가 어떤 최상위 디렉토리에 속해 있는지 찾는 데 사용된다.
    
    * 예를 들어, 파일 "file.txt"가 어느 디렉토리에 포함되어 있는지 알고 싶다면 `Find_Set(file.txt)`를 호출하여 "file.txt"의 최상위 디렉토리를 찾을 수 있다. 이를 통해 파일 위치를 빠르게 확인할 수 있게된다.
        

#### 구체적인 예제

* **디렉토리 초기화**: 디렉토리 "A"와 "B"를 각각 독립 디렉토리로 초기화
    
    * `Make_Set(A)`, `Make_Set(B)`
        
* **디렉토리 병합**: "A"와 "B"를 하나의 구조로 병합한다.
    
    * `Union(A, B)`: 이제 "B"가 "A"와 같은 상위 디렉토리를 공유하게 된다.
        
* **위치 확인**: 파일 "file1"이 속한 최상위 디렉토리를 찾으려면 `Find_Set(file1)`을 호출하여 속한 디렉토리의 루트 디렉토리를 빠르게 파악할 수 있다.
    

---

### **트리구조의 유니온 파인드 연산에서 효율성을 높이는 2가지 방법**  
**(2 Methods to Increase Efficiency in Union-Find Operations)**

* **랭크를 이용한 유니온** (**Union by Rank**)
    
* **경로 압축** (**Path Compression**)  
    

**<mark>💡요약: </mark>** 유니온 파인드에서 **랭크**와 **경로 압축**을 사용하면 트리의 높이가 줄어들어 **탐색 연산의 속도**를 향상시킬 수 있게 된다. 랭크가 낮은 트리를 높은 트리에 붙이고, 경로 압축을 통해 방문하는 노드를 루트에 바로 연결할 수 있다.  

1. **랭크를 이용한 유니온 (Union by Rank)**
    
    * 두 집합을 합칠 때, **랭크** (**Rank**), 즉 트리의 **높이**를 기준으로 작은 집합을 큰 집합에 붙인다.
        
    * 이 방법을 사용하면 트리의 높이를 최소화하여 **탐색 시간을 줄일 수 있다**. 예를 들어, A라는 집합과 B라는 집합이 있을 때, A의 랭크가 더 높다면, B를 A에 합친다.
        
2. **경로 압축 (Path Compression)**
    
    * **Find\_Set** 연산을 수행할 때, **모든 노드가 직접 루트 노드(Direct root node)를 가리키도록 부모 포인터를 변경**하는 최적화 기법이다.
        
    * 즉, 경로 압축은 한 번 루트를 찾는 과정에서 만난 모든 중간 노드들이 다음 탐색 시에는 바로 루트에 접근할 수 있도록 부모 포인터를 루트로 설정해 준다. 이렇게 하면 트리의 깊이가 줄어들어 이후의 탐색 속도가 빨라지게 된다.
        
    * 예를 들어, 노드 x가 루트까지 가기 위해 여러 개의 부모 노드를 거쳐야 하는 상황에서 경로 압축을 적용하면, 한 번 루트를 찾고 나면 x와 그 중간의 모든 노드들이 루트를 직접 가리키게 된다. 이후로는 탐색할 때 루트에 바로 도달할 수 있어 탐색 시간이 크게 단축되는 것이다.
        
3. **랭크 (Rank)**
    
    * 여기서 랭크는 각 노드에서 자신을 루트로 하는 **서브트리의 높이**를 의미한다. 랭크를 통해 트리의 균형을 유지할 수 있다.  
        

**<mark>💡예제: </mark>** 학교의 학급을 예로 들어보면, 각 학급이 서로 다른 그룹으로 시작할 수 있다. **랭크를 이용한 유니온**은 학생 수가 적은 학급을 큰 학급에 합치는 것과 비슷하며, **경로 압축**은 학급장이 바뀌었을 때, 모든 학생이 새로운 학급장을 바로 알 수 있게 연결하는 것과 같다.

---

### **트리구조 - 랭크를 이용한 Union의 예** (**Example of Union by Rank**)

**<mark>💡요약: </mark>** 두 개의 집합을 합칠 때 **트리의 높이** (**Rank**)를 기준으로 더 낮은 랭크의 트리를 더 높은 랭크의 트리에 붙여서 트리의 높이가 불필요하게 커지지 않도록 한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731028265069/9cf9f160-b9ac-4368-b062-c7bb998f8075.png align="center")

* **합치고자 하는 두 집합**
    
    * 왼쪽 트리는 c를 루트로 하는 집합이고, c의 랭크는 2이다. 오른쪽 트리는 e를 루트로 하는 집합이고, e의 랭크는 1이다.
        
    * 각 노드의 랭크는 파란색 상자 안에 표시되어 있으며, 각 노드에서 루트 노드까지의 높이를 나타낸다.
        
* **랭크 비교 후 트리 합치기**
    
    * 두 트리를 합칠 때, 랭크가 낮은 쪽의 루트 노드 e를 랭크가 높은 쪽의 루트 노드 c에 붙인다. 이는 트리의 높이를 최소화하기 위한 방법이다.
        
* **합쳐진 결과**
    
    * e가 c를 가리키도록 연결되며, 이제 모든 노드가 루트 노드 c를 공유하는 하나의 트리로 합쳐지게 된다. 이 결과, 트리의 높이가 불필요하게 증가하지 않으며 효율성을 유지할 수 있다.
        

**<mark>💡예제: </mark>** 학교의 두 동아리가 하나로 합쳐질 때, 인원이 많은 동아리의 리더가 전체 리더가 되는 상황을 생각해볼 수 있다. 인원이 적은 동아리의 리더와 멤버들은 큰 동아리의 리더를 따르도록 함으로써, 관리 구조가 복잡해지지 않게 한다.

---

### **랭크를 이용한 Union에서 랭크가 증가하는 예**  
(**Example of Rank Increase in Union by Rank**)

**<mark>💡요약: </mark> 랭크를 이용한 Union**에서 두 집합의 **랭크가 같을 때** 합치면 **하나의 랭크가 증가**하게 된다. 이는 트리의 높이를 최소화하면서도 균형을 유지하는 방식이다.  

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731030203473/80d357ac-021f-4c0d-ab1b-d337072e51f2.png align="center")

* **합치고자 하는 두 집합**
    
    * 왼쪽에는 대표 노드가 c이고 랭크가 2인 집합이 있으며, 오른쪽에는 대표 노드가 e이고 랭크가 2인 집합이 있다.
        
    * 두 집합의 랭크가 같기 때문에, 두 집합을 합칠 때 한쪽의 랭크가 증가하게 된다.
        
* **동일한 랭크의 두 집합을 합치기**
    
    * 두 집합의 대표 노드가 모두 랭크 2를 가지고 있기 때문에, 하나의 대표 노드를 다른 대표 노드에 붙이는 대신에 한쪽의 랭크를 3으로 증가시키고 나머지 대표 노드가 이 새로운 대표 노드를 가리키도록 한다.
        
* **합쳐진 결과**
    
    * e가 c를 가리키도록 변경되며, 이로 인해 c의 랭크가 3으로 증가하게 된다. 합쳐진 트리의 루트는 c가 되고, 이제 트리 전체는 하나의 집합으로 관리된다.
        

**<mark>💡예제: </mark>** 두 그룹이 통합될 때, 두 그룹의 리더의 지위가 같다면, 하나의 리더가 전체 리더가 되고 그 리더의 지위(랭크)가 증가하는 상황을 생각할 수 있다.

---

### **랭크를 이용한 Union과 Make\_Set의 의사 코드**  
(**Pseudocode for Union by Rank and Make\_Set**)

**<mark>💡요약: </mark> 랭크를 이용한 Union**은 두 집합의 랭크를 비교하여 **랭크가 낮은 트리를 높은 트리에 붙여 트리의 깊이를 최소화**하는 방식이다. 랭크가 같을 경우, 합쳐진 트리의 랭크가 하나 증가한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731030282553/b5aaed6f-7207-478e-8101-21e20ac041c0.png align="center")

* `Make_Set(x)`
    
    * **Make\_Set(x)** 연산은 새로운 집합을 만든다.
        
    * **x.parent ← x**는 노드 x가 자기 자신을 부모로 가리키게 하고, **x.rank ← 0**은 x의 랭크를 0으로 초기화한다.
        
* `Union(x, y)`
    
    * **Union(x, y)** 연산은 두 집합을 합칩니다.
        
    * **x' ← Find\_Set(x)**와 **y' ← Find\_Set(y)**를 통해 각 집합의 대표 노드를 찾는다.
        
    * **if (x'.rank &gt; y'.rank)**: x의 랭크가 y의 랭크보다 크다면, y의 부모를 x로 설정한다. (**y’.parent ← x'**).
        
    * **else**: 반대의 경우, x의 부모를 y로 설정하고, 만약 두 랭크가 같다면, y의 랭크를 1 증가시킨다 (**y’.rank ← y’.rank + 1**).
        

**<mark>💡예제: </mark>** 두 그룹이 통합될 때, 두 그룹의 리더의 지위가 같다면, 하나의 리더가 전체 리더가 되고 그 리더의 지위(랭크)가 증가하는 상황을 생각할 수 있다.

---

### **트리구조 - 경로 압축의 예** (**Example of Path Compression**)

**<mark>💡요약: </mark> 경로 압축** (**Path Compression**)은 유니온 파인드에서 `Find_Set`연산을 수행할 때, 탐색 경로에 있는 모든 노드가 직접 **루트 노드** (**Root Node**)를 가리키도록 하여 트리의 깊이를 줄이는 최적화 기법이다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731030453393/4cd525c8-f7a1-4153-a247-b12076e25942.png align="center")

* **초기 상태**
    
    * 왼쪽 그림에서, g 노드가 루트 c까지 가기 위해 e와 h를 거쳐야 한다. 현재 g와 루트 c 사이에 여러 중간 노드가 있다.
        
* **Find\_Set(g) 수행**
    
    * **Find\_Set(g)**를 실행하여 g가 속한 집합의 대표 원소(루트)를 찾는다. 이 과정에서 g에서 e, h, 그리고 최종적으로 루트 c까지 도달한다.
        
* **경로 압축 후 결과**
    
    * 경로 압축을 통해 g와 경로에 있는 중간 노드들이 모두 **루트 c를 직접 가리키도록** 변경되었다. 오른쪽 그림처럼, 이제 g, e, h는 모두 c를 직접 가리키게 되어 트리의 높이가 줄어들고, 다음 탐색이 더 빨라진다.
        

**<mark>💡예제: </mark>** 학교에서 학생들이 교장 선생님을 만나려면, 여러 단계를 거쳐야 하는 상황을 생각할 수 있다. 경로 압축을 적용하면, 한 번 만난 후 모든 학생이 바로 교장 선생님을 찾아갈 수 있도록 경로가 단순화된다.

---

### **트리구조 - 경로 압축을 이용한** `Find_Set` (**Find\_Set with Path Compression**)

**<mark>💡요약: </mark>** 경로 압축을 적용한 `Find_Set`은 노드가 속한 트리의 **루트**를 찾을 때, 경로에 있는 모든 노드가 직접 루트를 가리키도록 부모를 설정하여 **탐색 효율을 높인다**.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731030666906/0a23bda4-2715-4f4c-b7fc-b6e147d41e17.png align="center")

* **Find\_Set(x)**:
    
    * **Find\_Set(x)**는 노드 x가 속한 트리의 **루트 노드** (**Root Node**)를 찾는다.
        
    * **if (x.parent ≠ x)**: 만약 x가 자기 자신을 부모로 가리키지 않는다면, 즉, x가 루트 노드가 아니라면, 경로 압축을 적용한다.
        
    * **x.parent ← Find\_Set(x.parent)**: 경로 압축을 통해 x의 부모를 **재귀 호출**로 찾은 루트 노드로 설정한다. 이를 통해 x와 그 상위 노드들이 루트를 직접 가리키게 된다.
        
    * 마지막으로 **return x.parent**를 통해 최종 루트를 반환한다.
        
* **경로 압축의 역할**
    
    * 경로 압축을 통해 노드 x와 그 상위 노드들이 모두 루트 노드를 가리키게 되므로, 이후의 탐색에서 트리의 깊이가 감소하여 **탐색 속도가 빨라지게 된다.**
        

**<mark>💡예제: </mark>** 회사에서 직원들이 상위 관리자(루트)를 찾는 과정을 생각할 수 있다. 경로 압축을 적용하면, 한 번 경로를 찾은 이후로 모든 직원이 바로 상위 관리자에게 연결되어, 다음에 상위를 찾을 때 더 빠르게 도달할 수 있다.

---

### ❓**수행 시간** (**Time Complexity**)  
: **랭크** (**Rank**)와 **경로 압축** (**Path Compression**)을 사용하여 유니온 파인드를 최적화했을 때, 연산이 얼마나 효율적으로 수행될까?❓

**<mark>💡요약: </mark> 랭크**와 **경로 압축**을 사용하면 유니온 파인드의 수행 시간은 **거의 선형적**(**Almost Linear**)이 다. 이는 \*\*log ∗ n\*\*이 매우 느리게 증가하기 때문에, 많은 연산을 수행해도 시간 복잡도가 효과적으로 관리됨을 의미한다.

  
**수행 시간**

* **랭크와 경로 압축을 사용한 유니온 파인드**에서는 m번의 `Make_Set`, `Union`, `Find_Set` 연산을 수행할 때, 각 연산의 **평균적인 시간 복잡도**가 O(m⋅log⁡∗n)이 된다. 여기서 n은 집합의 개수를 나타낸다.
    

* **log\* n**
    
    * \*\*log\*n\*\*은 매우 느리게 증가하는 함수로, n이 엄청나게 큰 값이더라도 매우 작은 수로 제한된다. 이는 **사실상 상수 시간** (**Almost Constant Time**)과 비슷한 수준의 효율성을 보여준다.
        
    * \*\*log\* n\*\*는 여러 번 로그를 반복하여 계산하며, n이 작을수록 빠르게 1 이하가 되기 때문에 실용적인 문제에서 매우 효율적이다.
        

  
**"사실상 선형시간임"**

* O(m ⋅ log\* n)는 m번의 연산이 거의 선형 시간에 가까운 속도로 수행된다는 의미로, **유니온 파인드가 매우 효율적임**을 강조할수 있다.
    

**<mark>💡예제: </mark>** 학교에서 수천 명의 학생이 소속된 동아리 활동을 관리할 때, 랭크와 경로 압축을 사용하면 각 학생의 대표(리더)를 빠르게 찾을 수 있다. 학생이 많아도, 탐색 과정에서 경로를 최적화하여 매우 효율적으로 리더를 찾는 것과 같은 원리이다.

###   
❓연결리스트와 트리구조의 **수행 시간** (**Time Complexity**)비교

**연결 리스트의 Make\_Set과 Find\_Set**은 상수 시간에 동작할 수 있지만, 트리 구조를 관리하는 유니온 파인드만큼 효율적으로 많은 집합을 병합하거나 찾는 데 최적화되지 않는다.

**유니온 파인드의 O(m⋅log⁡∗n)** 수행 시간은 더 큰 데이터셋을 다루면서도 거의 선형에 가깝게 빠르게 연산할 수 있어, **많은 집합을 관리하는 문제에서는 연결 리스트보다 훨씬 효율적**이다.

따라서, **유니온 파인드가 연결 리스트보다 훨씬 더 큰 규모의 데이터 관리에서 효율적**이라고 할 수 있다.

---

## **4️⃣** 파이썬의 1차원 리스트 구현  
(Implementation of 1-Dimensional List in Python)

**<mark>💡요약: </mark> 1차원 리스트를 이용한 초기화**는 각 노드를 처음에 자기 자신이 대표가 되도록 설정하여, 초기 상태에서의 독립된 집합을 표현한다. 리스트는 각 노드의 대표를 나타내며, 인덱스 값으로 초기화된다. **1차원 리스트**를 사용하여 초기 상태에서 각 노드를 **대표 노드** (**Representative Node**)로 설정하는 방법을 더 자세히 알아보자  

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731034458601/0b09e6e8-e569-4671-a59f-73c487e87ca9.png align="center")

**각 노드는 처음에 연결되지 않음**

* 초기 상태에서는 모든 노드가 서로 연결되어 있지 않기 때문에, 각 노드는 자기 자신이 대표 노드가 된다.
    

**리스트의 초기화**

* 리스트의 각 위치는 해당 노드의 대표 노드를 나타낸다. 예를 들어, 노드 1의 대표는 1, 노드 2의 대표는 2가 된다.
    
* 따라서, 리스트는 각 노드의 **인덱스 값** (**Index Value**)으로 초기화된다.
    

**<mark>💡예제: </mark>** 예를 들어, 학생 번호가 1번부터 6번까지 있는 그룹을 만든다고 가정합니다. 각 학생은 처음에는 자신이 속한 그룹의 대표가 된다. 따라서 1번 학생의 대표는 1이고 2번 학생의 대표는 2가 되는 식이다.

---

### **1차원 리스트를 이용한 Union 연산**  
(**Union Operation Using a 1-Dimensional List**)

**<mark>💡요약: </mark> Union 연산**을 통해 두 노드를 같은 집합으로 연결한다. 각 노드의 대표 노드를 찾아 리스트에서 업데이트하며, 이를 통해 효율적으로 집합을 관리할 수 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731034633158/48a62901-a2bd-4394-b35f-bd1ff5bae20f.png align="center")

**Union 연산의 단계**

* **union(1, 4)**: 첫 번째로, 노드 1과 4를 연결한다. 여기서 각 노드의 대표 노드를 찾고, 1과 4를 연결한다.
    
* **union(5, 6)**: 두 번째로, 노드 5와 6을 연결한다. 마찬가지로 각 노드의 대표 노드를 찾아 연결한다.
    
* **union(4, 6)**: 세 번째로, 4와 6을 연결하려고 한다. 이때, 4와 6의 대표 노드를 찾은 후, 대표 노드 1과 5를 연결하여 하나의 집합으로 만든다.
    

**유니온 파인드 리스트 변화**

* 각 연산 후에 리스트에서 대표 노드가 갱신된다. 예를 들어, union(4, 6)을 수행한 후에는 1, 4, 5, 6이 동일한 대표 노드(1)를 가리키게 된다.  
    

**<mark>💡예제: </mark>** 동아리 학생들이 각자 다른 팀으로 나뉘어 있다가, 두 팀이 합쳐져 하나의 그룹이 될 때 각 팀의 대표가 모여 새 대표를 정하는 과정과 유사하다.

---

### **1차원 리스트 - Find 연산**과 **경로 압축**을 이용하여 **대표 노드** 찾기 (Find Representative Node using **Find Operation** & **Path Compression**)

**<mark>💡요약: </mark> Find 연산**은 노드가 속한 집합의 대표 노드를 찾고, 경로 압축을 통해 탐색 속도를 향상시킨다. 경로 압축을 통해 각 노드가 바로 대표 노드를 가리키도록 만들어, 이후 연산에서 더 빠르게 접근할 수 있게 한다.

**Find 연산의 작동 원리**

* **① 대상 노드 리스트에 index값과 value값이 동일한지 확인**  
    Find 연산은 현재 노드의 인덱스와 값이 같은지 확인한다. 이는 노드가 자기 자신을 가리키는지 확인하는 과정이다.
    
* **② 동일하지 않으면 value값이 가리키는 index 위치로 이동**  
    만약 인덱스와 값이 다르다면, 값이 가리키는 인덱스 위치로 이동하여 다시 확인한다.
    
* **③ 이동 위치의 index값과 value값이 같을 때까지 반복**  
    인덱스와 값이 같을 때까지 이 과정을 반복한다. 이 과정은 재귀 함수로 구현할 수 있다.
    
* **④ 대표 노드에 도달하면 경로 상의 모든 노드를 대표 노드로 변경**  
    대표 노드를 찾으면, 탐색 경로에 있던 모든 노드의 값을 대표 노드로 변경하여 **경로 압축**을 수행하게 된다.
    

**<mark>💡예제: </mark>** 학생들이 각자 소속된 동아리의 대표를 찾는 과정이라고 생각할 수 있다. 학생들이 대표를 찾기 위해 계속해서 상위로 올라가지만, 한 번 대표를 찾으면 이후에는 각자 바로 대표를 가리키도록 하여 다음 탐색이 더 빨라지게 된다.

---

### **1차원 리스트 - Find 연산**과 **경로 압축**의 동작방식 (How **Find Operation** & **Path Compression works**)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731034949245/e71c86cb-c987-4737-83d8-80f770f72b70.png align="center")

* **Find(6) 연산의 시작**: 노드 6의 대표 노드를 찾기 위해 A\[6\]을 확인합니다.
    
    * **① A\[6\] != 6이므로** 인덱스와 값이 같지 않다. 따라서, 값이 가리키는 인덱스로 이동하여 A\[5\]를 확인한.
        
    * **② A\[5\] != 5이므로** 다시 이동하여 A\[1\]을 확인한다.
        
    * **③ A\[1\] == 1이므로** 인덱스와 값이 같아, 노드 1이 대표 노드임을 확인할 수 있다.
        
* **경로 압축**: 대표 노드(1)를 찾은 후, 탐색 경로에 있던 모든 노드의 값을 대표 노드의 값으로 변경하여 다음 탐색 시 더 빠르게 접근할 수 있게 한다.
    

**<mark>💡예제: </mark>** 학생이 소속된 동아리 대표를 찾는 상황을 생각해볼 수 있다. 처음엔 누가 대표인지 모르기 때문에 여러 사람에게 물어봐야 하지만, 대표를 알게 된 후에는 다른 사람들도 바로 대표를 가리키도록 하여, 다음에 또 물어볼 때 더 빠르게 대표를 찾을 수 있게 된다.

---

### **1차원리스트 - Find 연산**과 **경로 압축**을 통해 효율적으로 데이터를 관리하는 방법 (Increase Data management efficiency using **Find Operation** & **Path Compression)**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731035071878/759eeb18-045c-4b24-a9e1-cb92461f2454.png align="center")

**<mark>💡요약: </mark> Find 연산**은 특정 노드의 대표 노드를 찾아주는 연산인데, 경로 압축을 사용하면 이후의 Find 연산 속도가 빨라지게 된다.

* **연산의 복잡도 감소**: 경로 압축을 통해 모든 노드가 직접 대표 노드와 연결되므로 **시간 복잡도**가 줄어들게 된다.
    
* **대표 노드와 바로 연결**: Find 연산을 실행할 때 경로에 있는 노드들이 대표 노드와 바로 연결되도록 업데이트된다.
    
* **연산 속도 향상**: 경로 압축이 완료된 후에는 Find 연산이 **O(1)**의 시간 복잡도로 매우 빠르게 수행될수 있다.
    

**<mark>💡예제:</mark>**

* 첫 번째 행은 초기 상태로 각 노드가 자기 자신을 가리키고 있다.
    

* 두 번째 행은 Find 연산을 수행하면서 경로를 압축하는 과정이다.
    
* 세 번째 행은 모든 노드가 대표 노드 1을 가리키게 되어, 이후 Find 연산이 매우 빨라지는 상태가 된다.
    

---

### 1차원 리스트를 사용하여 집합을 표현하기

**<mark>💡요약: </mark>** 아래 알고리즘은 각 원소가 포함된 집합을 간단히 표현하고 관리하기 위한 방법을 제공하고 있다. 초기에 `{0}, {1}, {2}, ... {n}`과 같은 집합이 각각 독립적으로 존재하며, 이들을 **합집합 연산**과 **같은 집합에 포함 여부 확인 연산**을 통해 관리한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731035341962/daa709e9-c596-4f3d-861d-a261f8329f67.png align="center")

* **합집합 연산** (**Union Operation**): 두 원소가 속한 집합을 하나로 합친다. 입력 형식은 `0 a b`로, 원소 `a`와 `b`가 속한 집합을 합친다.
    
* **같은 집합에 포함 여부 확인 연산** (**Find Operation**): 두 원소가 같은 집합에 포함되어 있는지 확인한다. 입력 형식은 `1 a b`로, 원소 `a`와 `b`가 같은 집합에 속하는지 확인한다.
    

**<mark>💡예제:</mark>**초기 집합이 `{0}, {1}, {2}, {3}`일 때:

* `0 1 2` 연산을 수행하면 `{1, 2}`가 같은 집합이 된다.
    
* `1 1 2` 연산을 수행하면 `1`과 `2`가 같은 집합에 속해 있다는 결과를 확인할 수 있다.
    

---

### 1차원 리스트를 사용하여 집합을 표현하기- 출력(Output)

**유니온-파인드 (Union-Find)** 알고리즘을 통해 집합을 표현하고, 집합 간의 연산을 효율적으로 처리하는 방식이다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731035479623/5b8e61bd-dfdd-436c-a261-9ef1d54a3fb4.png align="center")

1. **입력 형식**:
    
    * 첫 번째 줄은 `n` (원소 개수)와 `m` (질의 개수)을 나타낸다.
        
    * 이후 각 줄에 `0 a b` 또는 `1 a b`의 형식으로 연산이 주어진다.
        
        * `0 a b`: 원소 `a`와 `b`가 속한 집합을 **합집합**이다.
            
        * `1 a b`: 원소 `a`와 `b`가 **같은 집합에 포함되어 있는지 확인**한다.
            
2. **출력 형식**:
    
    * `1`로 시작하는 연산의 결과를 YES 또는 NO로 출력한다.
        
    * YES는 `a`와 `b`가 같은 집합에 속해 있음을 의미하고, NO는 다른 집합에 속해 있음을 나타낸다.
        

### 예제 설명

* **예제 입력**:
    
    * `7 8`: 원소 7개와 8개의 연산이 주어진다.
        
    * `0 1 3`: 원소 `1`과 `3`을 같은 집합으로 만든다.
        
    * `1 1 7`: 원소 `1`과 `7`이 같은 집합인지 확인 -&gt; NO
        
    * `0 7 6`: 원소 `7`과 `6`을 같은 집합으로 만든다.
        
    * `1 7 1`: 원소 `7`과 `1`이 같은 집합인지 확인 -&gt; NO
        
    * `0 3 7`: 원소 `3`과 `7`을 같은 집합으로 만든다.
        
    * `1 1 6`: 원소 `1`과 `6`이 같은 집합인지 확인 -&gt; YES
        
* **예제 출력**:
    
    * 각 `1`로 시작하는 연산에 대해 `NO`, `NO`, `YES`가 순서대로 출력되었다.
        

---

### 집합 표현하기 - 문제 분석하기 #1

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731035760705/5d0b0c51-2c05-45a9-894f-9272156a3e3d.png align="center")

이미지에는 다양한 Union과 Find 연산이 나와 있다. 각 연산을 수행할 때마다 집합 상태가 어떻게 변하는지 시각적으로 보여주며, 결과로 YES 또는 NO가 출력된다.

1. `union(1, 3)`을 수행한 후에는 1과 3이 같은 집합에 속하게 된다.
    
2. `find(1)`과 `find(7)`을 비교해 **NO**가 출력된다. 이는 1과 7이 다른 집합에 있음을 나타낸다.
    
3. `union(7, 6)`을 수행하여 7과 6을 같은 집합으로 만들었다.
    
4. 이후 `find(7)`과 `find(1)`을 비교해 **NO**가 출력되었다.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731035851771/616839b8-31e0-4fc2-abea-9e27bd546c5d.png align="center")

* `union(3, 7)`을 수행하여 3과 7을 연결한 후, 대표 노드를 갱신한다.
    
* `union(4, 2)`을 수행하여 4와 2를 같은 집합으로 만든다.
    
* `union(1, 1)` 연산은 이미 같은 집합에 속한 원소이므로 불필요한 연산이다.
    
* `find(1) == find(1)` 연산을 통해 1과 1이 같은 집합에 속해 있는지 확인하고, 결과로 **YES**가 출력된다.
    

---

### 집합 표현하기 - 의사 코드 작성(Pseudocode)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731035914692/a1c8ee5f-6cbd-40c2-ad65-e062d7f5c8c5.png align="center")

* **Find 연산**: 특정 원소가 속한 집합의 대표 노드를 찾는다.
    
    * 만약 `a`가 대표 노드라면 그대로 반환하고, 그렇지 않다면 `a`의 대표 노드를 재귀적으로 찾아 반환한다.
        
    * **경로 압축**을 통해 `a`의 대표 노드 값을 갱신하여 추후 찾기 연산 속도를 향상시킨다.
        
* **Union 연산**: 두 원소가 속한 집합을 하나로 합친다.
    
    * `a`와 `b`의 대표 노드를 찾아, 하나의 대표 노드로 연결한다.
        
* **CheckSame 함수**: 두 원소가 같은 집합에 속해 있는지 확인하는 함수이다.
    
    * `a`와 `b`의 대표 노드를 찾아 비교하고, 같다면 **true**, 그렇지 않다면 **false**를 반환한다.
        
* **초기화 과정**:
    
    * 각 원소가 독립된 집합으로 초기화되어 자기 자신을 대표 노드로 갖도록 설정한다.
        
* **입력과 반복문 처리**:
    
    * `N`번 반복하여 각 노드의 대표 노드를 자기 자신으로 초기화한다.
        
    * `M`번 반복하여 입력된 질의를 처리한다. 질의가 `0`이면 **Union 연산**을, 그렇지 않으면 **CheckSame**을 수행하여 결과값을 출력한다.
        

**<mark>💡예제:</mark>**예를 들어, 다음과 같은 두 연산을 수행할 수 있다.

* `union(3, 7)`: 3과 7을 같은 집합으로 합친다.
    
* `checkSame(3, 7)`: 3과 7이 같은 집합에 속해 있는지 확인하여 **true** 또는 **false**를 반환한다.
    

---