[알고리즘/JAVA] 유니온 파인드 (Union-find, Disjoint-Set)
유니온-파인드(Union-Find)
유니온-파인드 알고리즘은 집합을 결합(Union, 합집합)하고 해당 Element가 소속된 집합을 찾아내는(Find) 알고리즘이다.
서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다.
그래프에서도 유용하게 사용되어 노드 간의 연결 관계를 확인하는 등으로 응용되어 자주 사용된다.
해당 알고리즘은 두 가지 기본 연산으로 구성된다.
- Union 연산: 여러 노드 중 두 노드를 선택하여 이들을 하나의 집합으로 연결한다. 이 연산을 통해 서로 연결된 노드들이 같은 집합에 속하게 된다.
- Find 연산: 특정 노드의 대표 노드를 찾아낸다. 두 노드의 대표 노드를 찾아낸다면 해당 노드들이 같은 집합에 속해 있는지를 확인할 수 있다.
유니온-파인드의 용도
집합 소속 여부 판단: 임의의 두 노드가 동일한 집합에 속해 있는지를 확인할 수 있다. 그래프라면 임의의 두 노드가 연결되었는지 (탐색 가능한지)를 판단할 수 있다.
경로 압축: Find 연산 중 경로 압축 기법을 사용하여, 그래프 내에서 노드 간의 경로를 최적화한다. 이것은 그래프를 정돈하여 탐색 속도를 빠르게 하고 시간 복잡도를 향상시키는 목적으로도 사용할 수 있다.
싸이클 탐지: 그래프 탐색 중에 새로운 연결(Edge)이 싸이클을 형성하는지를 감지할 수 있다.
- 단 무방향 그래프에서만 적용이 가능하다.
- 최소 신장 트리 구성 시 크루스칼 알고리즘에서 싸이클이 형성되지 않게 하는 역할로도 사용된다.
- 이 외에 싸이클 감지 방법으로는 DFS, 벨만 포드, 플로이드, 위상 정렬 등을 사용할 수 있었다.
유니온-파인드의 과정
초기화
대표 노드를 저장하는 1차원 배열을 만든다. 이 때 초기에는 노드가 연결되어 있지 않으므로 자기 자신이 대표 노드이다.
Union 연산
여러 노드 중 두 노드를 선택하여 이들을 하나의 집합으로 연결한다고 하였다.
알고리즘 관점에서는 위에서 선언한 1차원 배열의 대표 노드를 갱신해주어 하나의 집합으로 묶는 과정이다.
이 때 유의할 점은 Union 연산 시 항상 대표 노드끼리를 연결해 주어야 한다는 것이다.
과정은 아래와 같다.
- 연결할 두 개의 노드를 입력으로 받는다.
- 두 개의 노드의 대표 노드를 find()연산을 통해 찾는다.
- 대표 노드끼리의 union()을 진행한다.
Union 연산 시 대표 노드가 자기 자신일 경우
해당 그림에서는 Union(1, 4)과 Union(2, 5)를 수행한다. 이 때 (1, 4), (2, 5)의 경우 현재는 대표 노드가 자기 자신이므로 그대로 Union을 진행해주면 된다. Union(1, 4)를 예시로 들어보자.
- 노드 1, 노드 4에서 find() 연산을 수행해도 대표 노드는 자기 자신이다.
- 따라서 곧바로 둘 중 하나의 대표 노드를 다른 쪽의 대표 노드로 설정한다. 여기서는 노드 4의 대표 노드를 노드 1으로 설정하였다.
- 일반적으로 인덱스가 작은 노드를 부모 노드로 삼는 경우가 많다. 어느 쪽을 부모로 삼을지에 대한 규칙을 임의로 정해야 한다.
대표 노드가 자기 자신이 아닌 경우에서 Union
이번에는 Union(4, 6)의 연산을 수행해보자.
- 노드 4를 find() 연산을 수행하면 대표 노드는 1이다. (앞서 Union(1, 4)에서 변경된 상태)
- 노드 6에서도 find() 연산을 수행해보면 대표 노드로 5를 얻을 수 있다.
- 이 경우, 각각의 대표 노드(1과 5)를 비교하여 Union 연산을 수행한다.
- 노드 1의 대표 노드를 노드 5로 설정한다.
Find 연산
특정 노드의 대표 노드를 찾아낸다. 두 노드의 대표 노드를 찾아낸다면 해당 노드들이 같은 집합에 속해 있는지를 확인할 수 있다.
연산 과정
- 대상 노드 배열의 index값과 value값이 동일한지 확인
- 동일하지 않으면 value값이 가리키는 index로 이동
- 재귀 함수로 구현 : index와 value값이 같을 때 까지 → 대표 노드를 찾을 때 까지 반복
- 재귀 함수를 빠져나오면서 거치는 모든 노드 값들을 루트 노드 값으로 변경
- 위 그림에서 Find()를 재귀적으로 대표 노드와 인덱스가 같은 값이 나올 때 까지 호출하여 루트 노드를 찾아내었다.
- 해당 노드의 인덱스를 재귀적으로 반환받으면서 자신의 parent값으로 설정한다.
- 결과로 반환되는 값은 해당 인덱스의 노드의 대표 노드에 해당한다.
문제 : 유니온-파인드 구현 (백준 1717, 집합의 표현)
유니온-파인드를 공부하고 가장 기본적으로 연습해 볼 수 있는 문제이다. 위에서 설명했던 Union 연산을 통해 집합을 묶고, Find 연산을 통해서 집합해 속해있는지의 여부(YES/NO)를 출력하는 문제이다.
public class Main {
static int[] parent;
static void union(int n1, int n2){
int a = find(n1);
int b = find(n2);
if(a > b){
parent[b] = a;
}
else{
parent[a] = b;
}
}
static int find(int k){
if(parent[k] != k){
parent[k] = find(parent[k]);
}
return parent[k];
}
static boolean connected(int n1, int n2){
return find(n1) == find(n2);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
parent = new int[n+1];
for(int i = 0; i <= n; i++){
parent[i] = i;
}
StringBuilder sb = new StringBuilder();
for(int j = 0; j < m; j++){
st = new StringTokenizer(br.readLine());
int command = Integer.parseInt(st.nextToken());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
if(command == 0){
union(n1, n2);
}
else{
if(connected(n1, n2)){
sb.append("YES").append("\n");
}
else{
sb.append("NO").append("\n");
}
}
}
System.out.println(sb);
}
}
parent 배열: 각 노드의 부모 노드를 저장하는 배열이다. 초기에는 모든 노드가 자기 자신을 부모로 가진다.
union() : 두 노드 n1과 n2를 같은 집합으로 묶는 Union 연산을 수행한다.
- 먼저, find 함수를 사용하여 n1과 n2의 대표 노드(루트)를 찾는다.
- 그 후, 두 대표 노드를 비교하여 더 작은 쪽을 큰 쪽의 부모로 설정하여 하나의 집합으로 묶는다.
find() : 노드 k의 대표 노드를 찾는 Find 연산을 수행한다.
- 만약 k가 자기 자신을 부모로 가지고 있지 않다면, 재귀적으로 부모 노드를 따라 올라가 최종적으로 대표 노드를 찾는다.
- 이 과정에서 경로 압축이 일어나, 중간에 거치는 모든 노드가 직접 대표 노드를 가리키도록 설정된다.
connected(): 두 노드 n1과 n2가 같은 집합에 속해 있는지를 확인한다.
- find 연산을 통해 두 노드의 대표 노드를 비교하고, 같으면 true를, 다르면 false를 반환한다.
문제 : 집합의 크기 계산하기 (백준 4195, 친구 네트워크)
각 노드들을 Union 연산하여 하나의 대표 노드로 통합시키는 방법을 지금까지 작성해보았다. 이번에는 해당 집합에 속하는 노드들이 모두 몇 개인가를 함께 구해야 하는 문제이다.
public class Main {
static final int MAX = 2000002;
static int[] parent;
static int[] count;
static HashMap<String, Integer> map;
static void union(int n1, int n2){
int k1 = find(n1);
int k2 = find(n2);
if(k1 < k2){
parent[k2] = k1;
count[k1] += count[k2];
count[k2] = 0;
}
else if(k2 < k1){
parent[k1] = k2;
count[k2] += count[k1];
count[k1] = 0;
}
}
static int find(int n){
if(parent[n] != n){
parent[n] = find(parent[n]);
}
return parent[n];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int test = Integer.parseInt(st.nextToken());
StringBuilder sb = new StringBuilder();
for(int t = 0; t < test; t++){
parent = new int[MAX];
count = new int[MAX];
map = new HashMap();
int index = 1;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
for(int i = 0; i < n; i++){
String[] friends = br.readLine().split(" ");
for(int j = 0; j < 2; j++){
if(!map.containsKey(friends[j])){
map.put(friends[j], index);
parent[index] = index;
count[index] = 1;
index++;
}
}
union(map.get(friends[0]), map.get(friends[1]));
sb.append(count[find(map.get(friends[0]))]).append("\n");
}
}
System.out.println(sb);
}
}
해당 집합에 속하는 노드들이 모두 몇 개인가를 함께 구하기 위햐서 가장 1차원적으로 Parent 배열을 스캔하는 방법이 있긴 하겠지만 입력값이 크기 때문에 시간초과될 것이다.
따라서 count 배열을 추가적으로 만들어주어 Union 할 때 해당 크기를 갱신해주는 연산을 추가적으로 수행해주는 방법을 선택하였다.
- Union 연산 시 Parent가 되는 노드의 count 배열에 Child가 될 노드의 count를 추가시켜준다.
- Child의 count는 Parent에게 모두 주었으므로 0으로 설정한다.
그 밖에 유의해야 할 점으로는 다음 사항들이 있었다.
- F는 친구 관계의 수이다. 따라서 최대 2*F만큼의 노드가 존재할 수 있으므로 배열의 크기를 넉넉히 설정해 주어야 한다.
- Union 연산이 이미 수행된 관계, 즉 한번 입력된 친구 관계가 또다시 등장할 수 있다. 이것은 union 연산 시 k1과 k2가 같은 경우이다. 따라서 해당 관계에서는 parent 및 count의 갱신이 일어나면 안 된다.
- 노드가 String 형태로 주어지고, 노드의 수가 처음부터 주어지지 않는다. HashMap 등을 적절히 활용하여야 한다.
문제 : 유니온 파인드로 싸이클 판단 (백준 20040, 사이클 게임)
유니온-파인드 연산은 그래프 탐색 중에 새로운 연결(Edge)이 싸이클을 형성하는지를 감지할 수 있다고 하였었다.
새로운 연결이 추가될 때 다음의 과정을 수행하여 싸이클 여부를 판단할 수 있다.
- 같은 집합에 속해 있는지 확인: Find 연산을 사용하여, 간선이 연결하는 두 노드의 대표 노드를 찾는다.
- 만약 두 노드가 다른 집합에 속해 있다면, Union 연산을 사용하여 두 집합을 하나로 합친다. 이 경우 싸이클은 형성되지 않는다.:
- 두 노드가 이미 같은 집합에 속해 있는 경우 간선을 추가하면 그래프에 싸이클이 형성된다고 판단할 수 있다.
Union-find 싸이클 감지는 무방향 그래프에서만 사용할 수 있다는 것을 기억하자.
public class Main {
static int[] parent;
static boolean union(int n1, int n2){
int k1 = find(n1);
int k2 = find(n2);
if(k1 > k2){
parent[k1] = k2;
return false;
}
else if(k2 > k1){
parent[k2] = k1;
return false;
}
else{
return true;
}
}
static int find(int n){
if(parent[n] != n){
parent[n] = find(parent[n]);
}
return parent[n];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
parent = new int[n];
for(int i = 0; i < n; i++){
parent[i] = i;
}
int result = 0;
for(int i = 1; i <= m; i++){
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
if(union(n1, n2)){
result = i;
break;
}
}
System.out.println(result);
}
}
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘/JAVA] 그래프 위상 정렬 (Topological Sort) (0) | 2024.08.11 |
|---|---|
| [알고리즘/JAVA] 그래프 최단경로 : Floyd-Warshall (플로이드-워셜) (0) | 2024.07.11 |
| [알고리즘/JAVA] 그래프 최단경로 : Bellman-Ford (벨만-포드) (0) | 2024.07.10 |
| [알고리즘/JAVA] 그래프 최단경로 : Dijkstra (다익스트라) (0) | 2024.07.08 |
| [알고리즘/JAVA] 그래프 탐색 : DFS / BFS (깊이우선 탐색 / 너비우선 탐색) (0) | 2024.05.27 |
