Union Find란?
여러 개의 서로소 집합을 병합하고 서로 다른 원소들이 같은 집합에 속해있는지 아닌지를 판별하는데 사용하기 위한 알고리즘이다. 크게 makeSet(),Union(), Find() 세가지의 연산으로 이루어진다.
Union : 병합, 합집합을 의미한다.
Find : 원소가 어떤 집합에 속해 있는지 탐색한다.
서로소 집합 (상호 배타 집합)이란?
공통 원소가 공집합 뿐, 공통 원소가 없는 두 집합을 의미하는데, 공약수가 1뿐인 두 정수를 의미하는 서로소의 개념이 집합으로 확장된 것이다. 직 교집합이 존재하지 않고, 각 집합은 대표자를 통해 구분한다.

표현 방법
이러한 서로소 집합을 나타내는 방식에는 크게 두가지가 있다.
1. 연결 리스트
- 같은 집합의 원소들을 하나의 연결 리스트로 관리한다.
- 연결 리스트의 맨 앞 원소를 집합의 대표자로 결정한다.
- 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.

Union(a,b) 결과, a를 대표자로 b가 병합되었다.

2. 트리
- 하나의 집합을 하나의 트리로 표현한다.
- 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다.

Union(a,b) 결과, a를 대표자로 b가 병합되었다.

예시 코드
1. makeSet()
p = new int[V];
r = new int[V];
for (int i = 0; i < V; i++) {
p[i] = i; // 정점의 대표는 우선 각 정점
r[i] = 1; // 정점의 랭크(예. 인구수 기준)
}
아래의 그림과 같은 배열을 만든다.

2. find()
private static int find(int v) {
if (v != p[v]) {
return p[v] = find(p[v]);
} else {
return p[v];
}
}
각 원소들이 현재 가리키고 있는 부모가 누구인지 확인한다.

이때 원소2의 부모는 1, 원소 5의 부모는 3인 것을 알 수 있다.
3. Union(a,b)
private static boolean union(int a, int b) {
// start의 대표와 end의 대표가 다르면 true;
a = find(a);
b = find(b);
if (a == b) return false; // 사이클이 있다는 뜻
// 대표찾기 : 다르면? 합칠 수 있다
if (r[a] > r[b]) {
r[a] += r[b]; // a에 인구수 몰아주자!
p[b] = a; // b의 대표는 a야!
} else {
r[b] += r[a];
p[a] = b;
}
return true;
}
각 원소들의 대표를 찾은 뒤, 같은 부모를 갖고 있다면 false를 리턴한다.
만약 부모가 다르다면 rank가 더 높은 원소를 기준으로 병합한다.

만약 1과 3이 병합된다면, 1의 rank가 더 높으므로 1이 부모가 되고 3이 자식노드가 될 것이다.
예제
집합의 표현 (백준 1717번, 골드 5)
https://www.acmicpc.net/problem/1717
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 집합의표현 {
static int[] parent;
public static void main(String[] args) throws NumberFormatException, 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;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int order = Integer.parseInt(st.nextToken()); //합쳐라 or 같은집합인지 확인해라
int a = Integer.parseInt(st.nextToken()); //a가 있는 집합
int b = Integer.parseInt(st.nextToken()); //b가 있는 집합
if (order == 0) {
union(a, b);
} else if (order == 1) {
sb.append((isSameParent(a, b) ? "YES" : "NO") + "\n");
} else {
continue;
}
}
System.out.println(sb.toString());
br.close();
}
// x의 부모를 찾는 연산
public static int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
// y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
public static void union(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
if (x < y) {
parent[y] = x;
} else {
parent[x] = y;
}
}
}
// x와 y의 부모가 같은지 확인
public static boolean isSameParent(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return true;
}
return false;
}
}
'코딩테스트' 카테고리의 다른 글
[백준 10164] 격자상의 경로 (0) | 2024.11.05 |
---|---|
[알고리즘] 인덱스 트리 (3) | 2024.11.05 |
[알고리즘] 트리를 사용해서 구간합 구하기 (0) | 2024.10.22 |
[알고리즘] 시뮬레이션 (2) | 2024.10.08 |
[알고리즘] 2차원 배열에서의 Union Find 알고리즘의 적용 (0) | 2024.10.01 |