유니온 파인드 알고리즘
유니온 파인드 (Union-Find) ?
- 유니온 파인드(Union-Find)는 그래프의 연결성을 판별하기 위한 효율적인 자료구조이다. → 이를 통해 서로소 집합(Disjoint Set)을 관리하며, 다음과 같은 두 가지 주요 연산을 제공한다.
- Union: 두 집합을 합친다.
- Find: 특정 원소가 속한 집합(대표 원소)을 찾는다.
- 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다.
💡 유니온 파인드 핵심 개념 - 루트(대표원소)
- 각 집합은 고유한 루트 노드를 갖고 있으며, 모든 원소는 해당 루트를 참조한다.
- 두 원소가 같은 집합에 속하는지는 Find 연산으로 확인한다.
💡 유니온 파인드 - 구현
- 초기화 : 유니온 파인드 자료구조를 위한 새로운 집합을 생성한다. → 각각의 노드가 자기 자신을 가리키도록 설정한다. ( = 처음에는 자기 자신이 트리의 최상위 노드이다. )
// 초기화: 각 노드는 자기 자신을 부모로 가짐
for (int i = 0; i < size; i++) {
parent[i] = i;
}
- Find : 해당 원소가 속해있는 부분집합의 루트를 반환한다. → 두 원소가 서로 다른 부분집합에 속해있으면 두 부분집합을 Union해야 하기 때문에, 두 원소의 루트가 같은지 확인해봐야 한다 ! ( ex: find(1) -> return 2 )
// Find: 특정 원소의 루트(대표)를 찾음 (경로 압축 적용)
public int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // 경로 압축
}
return parent[node];
}
//
- Union : 두 원소가 속한 부분집합이 다르면 두 부분집합을 하나의 부분집합으로 합치는 연산을 수행해야 한다.
( ex: union(2, 4) )
// Union: 두 집합을 합침 (랭크 기반)
public void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 == root2) {
return;
}
parent[root1] = parent[root2]
}
💡 유니온 파인드 핵심 개념 - 경로 압축
- Find 연산을 최적화하기 위한 방법이다. → 편향 트리 방지
- 특정 원소의 루트를 찾을 때, 경로상의 모든 노드가 루트를 직접 가리키도록 설정하여 다음 연산의 효율성을 높인다. → O(n) -> O(1)
// Union: 두 집합을 합침 (랭크 기반)
public void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 == root2) {
return;
}
parent[root1] = parent[root2]
if (root1 != root2) {
// 랭크를 기준으로 합치기
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else {
parent[root2] = root1;
rank[root1]++;
}
}
}
💡 유니온 파인드 핵심 개념 - 랭크 기반 합치기(Union)
- Union 연산을 최적화하기 위한 방법이다.
- 두 집합을 합칠 때, 트리의 높이(랭크)가 낮은 집합을 높은 집합에 붙이는 방식으로 트리의 길이를 최소화한다. → 같으면 한 쪽 트리 아래에 다른 쪽 트리를 붙인다 ! (어떤 트리이든 상관 X)
// 초기화: 각 노드는 자기 자신을 부모로 가짐
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0; // 초기 랭크는 0으로 초기화
}
-------------------------------------------
// Union: 두 집합을 합침 (랭크 기반)
public void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 != root2) {
// 랭크를 기준으로 합치기
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else {
parent[root2] = root1;
rank[root1]++;
}
}
}
💡 유니온 파인드 - 시간 복잡도
- 경로 압축과 랭크 기반 합치기를 사용하면 유니온 파인드의 연산은 **거의 상수 시간**에 수행된다. ( 정확히는 역아커만 함수(α(n))의 시간 복잡도를 가진다. )
class UnionFind {
private int[] parent; // 부모 노드를 저장
private int[] rank; // 각 노드의 랭크(트리 높이)
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
// 초기화: 각 노드는 자기 자신을 부모로 가짐
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0; // 초기 랭크는 0
}
}
// Find: 특정 원소의 루트(대표)를 찾음 (경로 압축 적용)
public int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // 경로 압축
}
return parent[node];
}
// Union: 두 집합을 합침 (랭크 기반)
public void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 != root2) {
// 랭크를 기준으로 합치기
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else {
parent[root2] = root1;
rank[root1]++;
}
}
}
// 두 노드가 같은 집합에 속해 있는지 확인
public boolean isConnected(int node1, int node2) {
return find(node1) == find(node2);
}
public static void main(String[] args) {
UnionFind uf = new UnionFind(10);
// Union 연산
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
// Find 연산 및 연결 확인
System.out.println(uf.isConnected(1, 3)); // true
System.out.println(uf.isConnected(1, 4)); // false
// 추가 Union
uf.union(3, 4);
System.out.println(uf.isConnected(1, 5)); // true
}
}
문제: 집합의 표현 (백준 1717)
문제 링크
알고리즘 [접근 방법]
- 유니온 파인드 알고리즘(union, find)을 구현하기만 하면 어렵지 않게 해결할 수 있다.
해결 코드
- 문제에서 제시한 로직을 유니온 파인트 연산을 이용해 그대로 구현한 코드이다.
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[] parent; // 부모 노드 저장
static int[] rank; // 각 노드의 랭크(트리 높이)
static void makeSet(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; ++i) {
parent[i] = i;
rank[i] = 0;
}
}
static int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]); // 경로 압축
}
return parent[node];
}
static void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 != root2) {
// 랭크를 기준으로 union
if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else {
parent[root2] = root1;
rank[root1]++;
}
}
}
static boolean isConnected(int node1, int node2) {
return find(node1) == find(node2);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 집합의 개수: n + 1
m = Integer.parseInt(st.nextToken()); // 연산의 개수
makeSet(n + 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; ++i) {
st = new StringTokenizer(br.readLine());
int input = Integer.parseInt(st.nextToken());
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
if (input == 1) {
sb.append(isConnected(node1, node2) ? "YES" : "NO");
sb.append("\\n");
} else if (input == 0) {
union(node1, node2);
}
}
System.out.print(sb.toString());
}
}
정리
- 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별해야 할 땐, 유니온 파인드(Union-Find) 알고리즘을 사용하자 !
https://thin-azimuth-2a9.notion.site/GDG-144f4ee21c00803c8aaae0a2c160fb94?pvs=4
GDG 스터디 - 유니온 파인드를 이용해 집합 관계 확인하기 | Notion
유니온 파인드 알고리즘
thin-azimuth-2a9.notion.site
