유니온 파인드란?

1. 유니온 파인드(Union-Find, Disjoint Set)란?

여러 개의 노드가 있을 때, 각각이 어느 집합(그룹)에 속해 있는지 효율적으로 관리하는 자료구조입니다.
주로 "같은 그룹인지 확인", "두 그룹을 하나로 합치기" 같은 문제에 쓰입니다.

---

2. 대표적인 용도

• 그래프에서 사이클 판별
• 최소 스패닝 트리 (MST) (예: 크루스칼)
• 연결 요소 개수 세기 (방금 너 문제처럼)

---

3. 주요 기능 (2가지)

find(x)	x가 속한 그룹의 대표(parent)를 찾음
union(x, y)	x가 속한 그룹과 y가 속한 그룹을 합침

 

---

4. 동작 방식 (원리)

(1) find(x)

• x가 어느 그룹에 속했는지 찾아야 함.
• parent [x] == x 이면 대표 노드.
• 아니라면 대표를 찾아가며 갱신.

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

---

(2) union(x, y)

• x의 대표와 y의 대표를 찾아서 하나로 합침.
• 보통은 y를 x의 대표에 붙이거나 반대로 붙임.

 

function union(x, y) { parent[find(x)] = find(y); }

 

---