1️⃣ 유니온 파인드 개념
유니온 파인드(Union-Find)는 두 개 이상의 노드가 있을 때 특정 2개의 노드를 연결해 하나의 집합으로 묶는 'union' 연산, 두 노드가 같은 집합에 속해 있는지 판단하는 'find' 연산으로 이루어진 알고리즘이다. 쉽게 말해 2개의 노드를 하나의 집합으로 만들 수 있고, 특정 노드가 속한 집합의 대표 노드를 찾을 수 있다. 아래는 각 연산에 대한 설명이다.
- Union 연산 : 각 노드가 속한 집합을 하나의 집합으로 합치는 연산이다. 노드 a, b가 각각 a ∈ A, b ∈ B 일 때 union(a, b) 는 A ∪ B 를 말한다.
- Find 연산 : 특정 노드 a에 대해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A 일 때 find(a) 는 A 집합의 대표 노드를 반환한다.
이를 노드와 간선의 관계로 이해해보면 A노드와 B노드가 있을 때 union(A, B) 연산을 수행하면 A, B를 잇는 간선이 생긴다. 특별히 인접 리스트 등을 활용하지 않아도 둘은 연결되어있다고 판단할 수 있다. 즉, 연결되어있는 두 노드는 하나의 집합으로 묶이고, 대표 노드를 설정하게 된다.
일반적으로 'parent' 라고 불리는 1차원 배열을 사용하며, 이는 각 노드가 속한 집합을 나타내게 된다. 예를 들어 노드 a, b, c가 있을 때 a, b는 A 집합, c 는 B 집합이라고 한다면 parent 배열은 다음과 같이 나타낼 수 있다.
| 노드 (index) | a | b | c |
| 집합 | A | A | B |
이제 유니온 파인드의 원리를 코드와 함께 알아보자.
2️⃣ 유니온 파인드 원리
1) parent 배열 초기화
위에서 'parent'라고 불리는 1차원 배열을 활용한다고 했다. 이를 위해선 처음에 parent 배열을 초기화해줘야 한다. 처음에는 각 노드가 연결되어 있지 않기 때문에 각 노드의 대표 노드를 해당 노드 번호로 초기화해야 한다. 즉, 각 노드의 대표 노드를 자신의 인덱스 값으로 초기화한다. 1 ~ N 까지 노드가 있다고 가정하고 초기화하자. 코드로 보면 간단하게 이해할 수 있다.
public class Main {
static int[] parent;
public static void main(String[] args) {
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
}
2) union 연산
2개의 노드를 선택해 union 연산을 수행한다. 먼저 union(2, 4), union(3, 6)을 수행한다고 가정한다. union(2, 4)를 수행할 때 대표 노드를 2번 노드라고 하자. 그러면 2번, 4번 노드가 연결되면서 같은 집합에 속하게 된다. 대표 노드를 2번 노드라고 했으므로 4번 노드의 대표 노드도 역시 2번 노드가 되어야 한다. 이후 union(3, 6)도 수행하면 아래 그림처럼 된다.
public class Main {
static int[] parent;
static int N = 6;
public static void main(String[] args) {
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
union(2, 4);
union(3, 6);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
private static void find(int target) {
// find 로직
}
}
아직 find 연산을 알아보지 않았으니 우선은 두 노드가 하나의 집합이 되는 과정만 보자. union(2, 4)를 수행하면 각각 find(2), find(4)를 통해 해당 집합의 대표 노드를 찾는다. 처음 parent 배열에서 찾은 대표 노드는 각 노드의 인덱스 번호이다. 따라서 2 != 4 이기 때문에 parent[4] = 2 를 수행하면서 4번 노드의 대표 노드가 2번 노드로 바뀌게 된다. 그럼 이제 특정 노드의 대표 노드를 어떻게 찾는지 find 연산의 원리를 알아보겠다.
3) find 연산
private static int find(int target) {
if (target == parent[target]) {
return target;
} else {
return parent[target] = find(parent[target]);
}
}
해당 코드는 find 연산을 구현한 것이다. 코드는 생각보다 간단하지만 재귀적 구조이기 때문에 잘 이해해야 한다. 지금까지는 각 노드의 대표 노드가 해당 노드의 인덱스 번호였기 때문에 첫 번째 if문은 쉽게 이해가 갈 것이다. 즉, 처음 수행했던 union(2, 4)의 경우 find(2), find(4)가 순차적으로 일어나고 아래처럼 반환한다.
- find(2) : 2 == parent[2] 따라서 return 2
- find(4) : 4 == parent[4] 따라서 return 4
하지만 이후 union(4, 6)을 수행하면 어떤 일이 일어날까? 먼저 흐름을 보자. 참고로 이 땐 parent[4] = 2, parent[6] = 3 이다.
- find(4) : 4 != parent[4] (= 2) -> else 로 이동
- return parent[4] = find(parent[4]) -> find(parent[4]) 가 먼저 수행된다.
- find(parent[4]) : parent[4] = 2 이므로 find(2) 가 수행된다.
- find(2) : 2 == parent[2] 이므로 return 2
- 즉, 1번의 find(parent[4]) = 2가 되면서 parent[4] = 2가 된다.
- find (6) : 6 != parent[6] (= 3) -> else 로 이동
- return parent[6] = find(parent[6]) -> find(parent[6]) 가 먼저 수행된다.
- find(parent[6]) : parent[6] = 3 이므로 find(3) 가 수행된다.
- find(3) : 3 == parent[3] 이므로 return 3
- 즉, 1번의 find(parent[6]) = 3이 되면서 parent[6] = 3이 된다.
이제 다시 union 연산으로 돌아가자. 그러면 두 번의 find 연산의 결과를 비교한다.
a = 2, b = 3 이므로 2 != 3이다. 따라서 parent[b] = a 이므로 parent[3] = 2 가 된다. 최종 결과와 전체 코드는 다음과 같다.
public class Main {
static int[] parent;
static int N = 6;
public static void main(String[] args) {
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
union(2, 4);
union(3, 6);
union(4, 6);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
private static void find(int target) {
if (target == parent[target]) {
return target;
} else {
return parent[target] = find(parent[target]);
}
}
}
4) 주의할 점
실제로 parent 배열의 결과를 출력하면 1 2 2 2 5 3 이 나온다. 그런데 왜 마지막 6번 노드의 parent[6] 값이 3일까? 그건 union 연산의 원리를 보면 쉽게 알 수 있다. 결국 find 연산으로 찾은 특정 두 노드 집합의 대표 노드가 다를 경우 parent[b] = a 이기 때문이다. 따라서 주의할 점은 대표 노드를 찾을 때 parent 배열에서 찾으면 안된다. 당연한 말이겠지만 6번 노드가 속한 집합의 대표 노드를 찾기 위해선 find(6)을 수행하면 된다. 간혹 parent 배열로부터 값을 받아오는 실수를 할 수 있는데, 같은 집합에 속한 노드는 맞지만 대표 노드는 아닐 수 있기 때문에 find 연산을 사용하자.
