유니온 파인드(Union-Find) 알고리즘에 대해 공부 후 정리하였습니다.
유니온 파인드 (Union Find)
1️⃣ 개념
서로소 집합(Disjoint Set) 을 관리하는 자료구조
두 노드가 같은 집합에 속하는지 판별하거나, 두 집합을 합치는 연산을 효율적으로 수행
주로 그래프의 연결 관계 관리에 사용 (예: 크루스칼 MST)
2️⃣ 주요 연산
Find(x)
- 원소 x가 속한 집합(대표 노드)을 찾음
- 경로 압축(Path Compression) 최적화를 적용하면 트리가 납작해짐
Union(a, b)
- 원소 a와 b가 속한 집합을 합침
- 랭크/사이즈 기반 합치기(Union by Rank/Size)로 트리 높이 최소화
3️⃣ 특징
- 간선 연결 여부나 집합의 동질성을 빠르게 확인 가능
- 그래프 문제에서 사이클 판별과 연결 요소 관리에 매우 효율적
- 크루스칼 알고리즘에서 필수
4️⃣ 시간 복잡도
- 단순 구현: Find = O(H) (H: 트리 높이)
- 경로 압축 + 랭크/사이즈 최적화 적용: 거의 O(1) (정확히는 α(N), 아커만 함수의 역함수)
5️⃣ 기본 코드 (최적화 없음)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class UnionFindBasic {
static int[] parent;
// 초기화
public static void init(int n) {
parent = new int[n + 1];
for (int i = 1; i <= n; i++) parent[i] = i;
}
// Find
public static int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]); // 경로 압축 없음
}
// Union
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) parent[b] = a;
}
public static void main(String[] args) {
init(5);
union(1, 2);
union(3, 4);
System.out.println(find(2) == find(1)); // true
System.out.println(find(2) == find(3)); // false
}
}
6️⃣ 최적화 적용 코드
방법 1. 경로 압축 (Path Compression)
- Find 실행 시, 탐색 경로의 모든 노드를 루트에 직접 연결
- 다음 호출 시 O(1)에 가까운 시간 복잡도
1
2
3
4
5
6
public static int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 루트를 바로 연결
}
return parent[x];
}
방법 2. 랭크/사이즈 기반 합치기 (Union by Rank/Size)
- 두 집합 합칠 때 작은 트리를 큰 트리에 붙임
- 트리 높이가 최소화되어 성능 향상
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static int[] rank;
public static void init(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 1; // 높이 1
}
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (rank[a] < rank[b]) {
parent[a] = b;
} else if (rank[a] > rank[b]) {
parent[b] = a;
} else {
parent[b] = a;
rank[a]++;
}
}
}
최적화 방법 2가지 결합
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class UnionFindOptimized {
static int[] parent, rank;
public static void init(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public static int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 경로 압축
}
return parent[x];
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (rank[a] < rank[b]) {
parent[a] = b;
} else if (rank[a] > rank[b]) {
parent[b] = a;
} else {
parent[b] = a;
rank[a]++;
}
}
}
public static void main(String[] args) {
init(5);
union(1, 2);
union(3, 4);
union(2, 3);
System.out.println(find(4) == find(1)); // true
}
}
유니온 파인드 활용
1️⃣ 무방향 그래프에서 사이클 판별
- 무방향 그래프에서 간선을 하나씩 추가하면서, 연결하려는 두 노드가 이미 같은 집합에 속해 있다면 → 사이클 발생
- Union-Find로 매우 빠르게 판별 가능 (O(E α(N)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;
public class CycleDetectionUF {
static int[] parent, rank;
public static void init(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public static boolean union(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false; // 이미 같은 집합 → 사이클 발생
if (rank[a] < rank[b]) parent[a] = b;
else if (rank[a] > rank[b]) parent[b] = a;
else {
parent[b] = a;
rank[a]++;
}
return true;
}
public static void main(String[] args) {
int n = 5; // 노드 개수
int[][] edges = {
{1, 2}, {1, 3}, {2, 3}, // (2, 3) 추가 시 사이클 발생
{3, 4}, {4, 5}
};
init(n);
boolean cycle = false;
for (int[] e : edges) {
if (!union(e[0], e[1])) {
cycle = true;
break;
}
}
System.out.println("사이클 존재 여부: " + cycle);
}
}
2️⃣ 2D 격자 병합 문제 (예: 같은 색 영역 합치기)
- N x M 격자에서 같은 색(또는 값)이 상하좌우로 연결되어 있으면 같은 그룹으로 묶기
- Union-Find를 이용하면 DFS/BFS 없이도 그룹 수 계산 가능
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class GridUnionFind {
static int[] parent, rank;
static int N, M;
public static void init(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (rank[a] < rank[b]) parent[a] = b;
else if (rank[a] > rank[b]) parent[b] = a;
else {
parent[b] = a;
rank[a]++;
}
}
}
public static void main(String[] args) {
int[][] grid = {
{1, 1, 0},
{1, 0, 0},
{0, 0, 1}
};
N = grid.length;
M = grid[0].length;
init(N * M);
// 방향: 상하좌우
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for (int x = 0; x < N; x++) {
for (int y = 0; y < M; y++) {
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (grid[x][y] == grid[nx][ny]) {
union(x * M + y, nx * M + ny);
}
}
}
}
}
// 고유 그룹 수 세기
java.util.Set<Integer> groups = new java.util.HashSet<>();
for (int i = 0; i < N * M; i++) {
groups.add(find(i));
}
System.out.println("고유 그룹 수: " + groups.size());
}
}