숏컷 코드
csharp
int Find(int x)
{
if (parent[x] == x) return x;
return parent[x] = Find(parent[x]);
}
bool Union(int a, int b)
{
int ra = Find(a);
int rb = Find(b);
if (ra == rb) return false;
parent[rb] = ra;
return true;
}구조
유니온-파인드는 여러 원소가 어떤 집합에 속하는지 관리합니다. 핵심 연산은 대표를 찾는 Find와 두 집합을 합치는 Union입니다.
text
Find(x): x가 속한 집합의 대표 찾기
Union(a, b): a와 b가 속한 집합 합치기처음에는 각 원소가 자기 자신을 대표로 갖습니다.
csharp
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;경로 압축
Find를 호출하면서 지나간 노드의 parent를 대표로 바로 연결하면 다음 탐색이 빨라집니다.
text
1 -> 2 -> 3 -> 4
Find(1) 후
1 -> 4, 2 -> 4, 3 -> 4랭크나 크기 기준으로 작은 트리를 큰 트리 아래 붙이면 높이가 커지는 것을 줄일 수 있습니다.
언제 쓰나
| 상황 | 판단 |
|---|---|
| 두 원소가 같은 그룹인지 반복 확인 | 유니온-파인드 |
| 연결 요소를 점진적으로 합침 | 유니온-파인드 |
| 무방향 그래프 사이클 감지 | Union 실패 여부 확인 |
| 크루스칼 MST | 간선 정렬 + 유니온-파인드 |
| 경로 자체가 필요 | BFS, DFS 검토 |
Union(a, b)에서 이미 같은 대표라면 두 정점은 이미 연결되어 있습니다. 무방향 그래프에서 새 간선이 사이클을 만드는지 확인할 때 이 성질을 씁니다.
주의할 점
유니온-파인드는 연결 여부를 빠르게 알려주지만, 실제 경로나 거리 정보는 알려주지 않습니다. “어떻게 연결되어 있는가”가 필요하면 그래프 탐색이 필요합니다.
또 재귀 Find는 트리가 깊으면 스택 문제가 생길 수 있으므로, 경로 압축과 크기 기준 합치기를 함께 쓰는 편이 안전합니다.
참고 링크
1 sources