TIL 2024-07-30 Union Find 알고리즘
Union Find 의미
Union Find는 Union + Find 를 합친 알고리즘이다.
그러므로 두 단어의 알고리즘적 의미를 알아야한다.
Union
Union은 합집합을 뜻한다.
1 ∈ A
2 ∈ B
일 때
A ∪ B = {1, 2} 가 된다.
Find
Find는 집합의 대표 노드를 반환하는 연산을 의미한다.
노드 a가 a ∈ A 일 때 find(a) 는 A집합의 대표 노드를 반환한다.
Union Find 원리 설명
1. 1차원 배열 이용 및 자기 자신 대표 노드로 초기화
유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용해서 표현한다.
배열을 처음 초기화 할 때는 union 연산을 따로 진행하지 않으므로 자기 자신의 대표 노드를 자신의 인덱스로 초기화한다.
int nodes = 5;
int[] parent = new int[nodes];
for (int i = 0; i < nodes; i++) {
parent[i] = i;
}
2. 두 개의 노드를 선택해 union 연산 수행
union(a, b) 는 a를 대표 노드, b를 자식 노드로 연산하라는 것이다.
다음과 같이 배열이 설정되어있다고 하자
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 3 | 4 |
union(0, 3) 을 수행한다.
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 0 | 4 |
union(1, 4) 을 수행한다.
| 0 | 1 | 2 | 3 | 4 |
| 0 | 1 | 2 | 0 | 1 |
union(0, 1) 을 수행한다.
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 2 | 0 | 1 |
여기까지가 union 연산만을 설명한 것이다.
union find가 되면 배열의 결과는 달라진다.
| 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 2 | 0 | 0 |
4번째 인덱스의 value 값이 0으로 바뀐다. 1번의 자식 노드가 4번이고 1번의 대표 노드가 0이니 자식 노드인 4도 1번과 동일한 자식 노드로 바뀌는 것이다.
public void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
3. Find 연산
Find 연산 작동 원리
- 대상 노드의 index 와 value 값이 동일한지 확인
- 동일하지 않다면 value 값이 가리키는 index 값으로 이동
- index 값과 value 값이 같아질 때 까지 재귀함수 형식으로 반복 (대표 노드 find)
- 대표 노드 도달 시 재귀 함수를 나오며, 거치는 모든 노드값을 루트 노드값으로 변경
find 연산은 시간 복잡도를 줄어들게 하는 효과를 가진다. 연산을 한번 거치고 나면 루트 노드값이 대표 노드로 바로 변경이 되어 노드 관련된 find 연산이 O(1)이 된다.
public int find(int a) {
if (parent[a] == a) { // 재귀 탈출 조건문
return a;
}
return parent[a] = find(parent[a]); // 재귀 및 탈출 시 대표노드 설정
}
연습 백준 문제
1717 - 집합의 표현
https://www.acmicpc.net/problem/1717
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] parent;
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 = 1; i <= N; i++) {
parent[i] = i;
}
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int question = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if (question == 0) {
union(a, b);
} else {
if (checkSame(a, b)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
public static int find(int a) {
if (a == parent[a]) {
return a;
} else {
return parent[a] = find(parent[a]);
}
}
public static boolean checkSame(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return true;
}
return false;
}
}
1976 - 여행 가자
https://www.acmicpc.net/problem/1976
정답 코드
import java.util.*;
public class Main {
static int[] parent;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int question = sc.nextInt();
if (question == 1) {
union(i, j);
}
}
}
int target = find(sc.nextInt() - 1);
boolean success = true;
for (int i = 0; i < M - 1; i++) {
if (target != find(sc.nextInt() - 1)) {
success = false;
}
}
if (success) {
System.out.print("YES");
} else {
System.out.print("NO");
}
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
public static int find(int a) {
if (parent[a] == a) {
return a;
}
return parent[a] = find(parent[a]);
}
}