유니온 파인드 — 그룹을 묶고 찾는 가장 빠른 방법
"이 두 노드는 같은 그룹에 속하는가?" 이 질문에 거의 O(1)로 답할 수 있는 자료구조가 있습니다.
유니온 파인드(Union-Find)란
유니온 파인드(Union-Find), 또는 서로소 집합(Disjoint Set Union)은 원소들이 속한 그룹을 관리 하는 자료구조입니다.
두 가지 핵심 연산을 제공합니다:
- Find(x): x가 속한 그룹의 대표(루트)를 반환
- Union(x, y): x가 속한 그룹과 y가 속한 그룹을 합침
왜 유니온 파인드가 필요한가
"두 원소가 같은 그룹인지 확인하고, 그룹을 합치는" 작업은 의외로 자주 등장합니다.
- 네트워크에서 두 컴퓨터가 연결되어 있는가?
- 크루스칼 알고리즘에서 간선을 추가해도 사이클이 안 생기는가?
- SNS에서 두 사용자가 같은 커뮤니티에 속하는가?
기본 구현
public class UnionFind {
private int[] parent;
private int[] rank;
private int count; // 그룹 수
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i; // 처음엔 자기 자신이 루트
}
}
// 기본 find — O(n) 최악
public int findBasic(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
// 기본 union
public void unionBasic(int x, int y) {
int rootX = findBasic(x);
int rootY = findBasic(y);
if (rootX != rootY) {
parent[rootX] = rootY;
count--;
}
}
}
이 기본 구현은 트리가 한쪽으로 치우칠 수 있어 find가 O(n)이 됩니다.
최적화 1: 경로 압축 (Path Compression)
find를 수행할 때, 경로 위의 모든 노드를 루트에 직접 연결합니다.
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 재귀적으로 루트를 찾아 직접 연결
}
return parent[x];
}
경로 압축 전: 경로 압축 후:
1 1
| / | \
2 2 3 4
|
3
|
4
최적화 2: Union by Rank
합칠 때 rank(높이 상한)가 작은 트리를 큰 트리 아래에 붙입니다.
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--;
}
Union by Size (대안)
size(원소 수)를 기준으로 합치는 방법도 있습니다.
private int[] size;
public UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
// 작은 트리를 큰 트리에 붙이기
if (size[rootX] < size[rootY]) {
parent[rootX] = rootY;
size[rootY] += size[rootX];
} else {
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
}
시간 복잡도
경로 압축 + union by rank를 모두 적용하면:
| 연산 | 시간 복잡도 |
|---|---|
| Find | O(α(n)) |
| Union | O(α(n)) |
α(n)은 역아커만 함수로, 실질적으로 모든 입력에 대해 5 이하입니다. ** 사실상 O(1)**이라고 보면 됩니다.
전체 구현
public class UnionFind {
private int[] parent;
private int[] rank;
private int count;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return false; // 이미 같은 그룹
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--;
return true;
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public int getCount() {
return count;
}
}
활용 1: 크루스칼 알고리즘
최소 신장 트리(MST)를 구하는 크루스칼 알고리즘에서 유니온 파인드가 핵심적으로 사용됩니다.
public static int kruskal(int n, int[][] edges) {
// 간선을 가중치 순으로 정렬
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
int totalWeight = 0;
int edgeCount = 0;
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
// 같은 그룹이면 사이클 → 건너뜀
if (uf.union(u, v)) {
totalWeight += w;
edgeCount++;
if (edgeCount == n - 1) break; // MST 완성
}
}
return totalWeight;
}
활용 2: 네트워크 연결 판별
// n개의 컴퓨터와 연결 목록이 주어질 때, 연결 요소 수 구하기
public static int numberOfNetworks(int n, int[][] connections) {
UnionFind uf = new UnionFind(n);
for (int[] conn : connections) {
uf.union(conn[0], conn[1]);
}
return uf.getCount();
}
활용 3: 섬의 개수 (2D 격자)
public static int numIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
UnionFind uf = new UnionFind(rows * cols);
int waterCount = 0;
int[] dx = {1, 0};
int[] dy = {0, 1};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '0') {
waterCount++;
continue;
}
for (int d = 0; d < 2; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni < rows && nj < cols && grid[ni][nj] == '1') {
uf.union(i * cols + j, ni * cols + nj);
}
}
}
}
return uf.getCount() - waterCount;
}
가중치 유니온 파인드
각 원소에 루트까지의 상대적 가중치를 저장하는 확장 버전입니다. "A는 B보다 3만큼 크다" 같은 관계를 관리할 수 있습니다.
public class WeightedUnionFind {
private int[] parent;
private int[] rank;
private long[] weight; // 부모까지의 가중치
public WeightedUnionFind(int n) {
parent = new int[n];
rank = new int[n];
weight = new long[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]);
weight[x] += weight[parent[x]]; // 가중치 누적
parent[x] = root;
}
return parent[x];
}
// x와 y의 관계: weight[y] - weight[x] = w
public boolean union(int x, int y, long w) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return weight[x] - weight[y] == w; // 모순 검사
}
// rootX를 rootY 아래에 붙이기
parent[rootX] = rootY;
weight[rootX] = weight[y] + w - weight[x];
return true;
}
}
백엔드/실무에서의 연결
분산 시스템의 노드 그룹
분산 시스템에서 네트워크 파티션이 발생했을 때, 어떤 노드들이 서로 통신 가능한지를 유니온 파인드로 관리할 수 있습니다.
이미지 처리의 Connected Component Labeling
이미지에서 연결된 픽셀 영역을 찾는 것은 유니온 파인드의 직접적인 응용입니다.
소셜 네트워크 친구 그룹
"A와 B가 친구이고, B와 C가 친구이면, A와 C는 같은 그룹"이라는 관계를 유니온 파인드로 관리합니다.
주의할 점
경로 압축 없이 union만 수행하여 시간 초과
경로 압축(Path Compression)과 union by rank를 모두 적용해야 find 연산이 사실상 O(1)입니다. 경로 압축 없이 단순 union만 하면 트리가 편향되어 O(n)이 됩니다.
union 호출 전에 find를 하지 않는 실수
parent[a] = b로 직접 연결하면 경로 압축이 적용되지 않습니다. 반드시 find(a)와 find(b)의 루트를 구한 뒤 루트끼리 연결해야 합니다.
정리
| 최적화 | 효과 |
|---|---|
| 경로 압축 | find 시 모든 노드를 루트에 직접 연결 |
| Union by Rank | 높이가 낮은 트리를 높은 트리에 붙임 |
| 둘 다 적용 | O(α(n)) ≈ 사실상 O(1) |
기억할 포인트:
- 유니온 파인드는 그룹 관리(합치기 + 같은 그룹인지 확인) 에 특화된 자료구조입니다.
- 경로 압축과 union by rank를 반드시 함께 적용하세요.
- 크루스칼 알고리즘에서 사이클 판별에 핵심적으로 사용됩니다.
- 실무에서는 네트워크 연결 상태, 클러스터링, 이미지 처리 등에 활용됩니다.
댓글 로딩 중...