15주차
- 여러 원소들을 몇 개의 그룹(집합)으로 묶어서 관리할 때 사용하는 자료구조
- Disjoint Set(서로소 집합)이라고도 부른다.
- 특정 원소가 어떤 집합에 속하는지, 두 원소가 같은 집합에 속하는지를 빠르게 확인할 수 있다.
- 트리 구조를 이용해서 각 집합을 표현한다. 같은 트리(같은 루트 노드)에 속한 원소들은 같은 집합이라고 본다.
Union-Find는 크게 두 가지 연산으로 이루어진다.
- Find: 특정 원소가 속한 집합의 루트(대표 원소)를 찾는 연산
- Union: 두 원소가 속한 집합을 하나로 합치는 연산
- 처음에는 모든 원소가 각자 자기 자신을 부모로 갖는 독립적인 집합이다.
parent[i] = i- Union 연산을 수행하면, 한쪽 집합의 루트가 다른 쪽 집합의 루트를 부모로 가리키게 된다.
- Find 연산을 수행하면, 부모를 계속 따라 올라가서 루트를 찾는다.
예를 들어 1, 2, 3, 4, 5라는 원소가 있고 (1, 2), (3, 4) 순서로 union을 수행하면 다음과 같은 집합이 만들어진다.
{1, 2}, {3, 4}, {5}
여기서 다시 (2, 3)을 union하면 다음과 같이 합쳐진다.
{1, 2, 3, 4}, {5}
ㅤ
- Find를 수행하는 과정에서 거쳐간 노드들을 모두 루트에 직접 연결해주는 최적화 기법
- 경로 압축을 하지 않으면 트리가 한쪽으로 길게 늘어져서(편향 트리) Find 연산이 느려질 수 있다.
- 경로 압축을 적용하면 이후의 Find 연산이 훨씬 빨라진다.
function find(parent, x) {
if (parent[x] === x) return x;
return (parent[x] = find(parent, parent[x])); // 경로 압축
}재귀 방식은 코드가 간결하지만, 원소 개수가 아주 많고 트리가 깊게 늘어져 있는 경우 재귀 호출이 쌓이면서 스택 오버플로우가 발생할 수 있다. 이런 상황이 걱정된다면 반복문으로도 동일하게 구현할 수 있다.
function find(parent, x) {
let root = x;
// 1. 루트를 먼저 찾는다
while (parent[root] !== root) {
root = parent[root];
}
// 2. 거쳐온 노드들을 모두 루트에 바로 연결한다 (경로 압축)
while (parent[x] !== root) {
const next = parent[x];
parent[x] = root;
x = next;
}
return root;
}두 집합을 합칠 때 무작정 한쪽을 다른 쪽 밑에 붙이면, 운이 나쁜 순서로 union이 반복될 경우 트리가 한쪽으로 길게 늘어질 수 있다. 이를 막기 위해 항상 더 작은 트리를 더 큰 트리 밑에 붙이는 방식을 사용하는데, 기준을 무엇으로 삼느냐에 따라 두 가지로 나뉜다.
- Union by Rank: 트리의 높이(rank)를 기준으로, 높이가 낮은 트리를 높은 트리 밑에 붙인다. 두 트리의 rank가 같을 때만 합쳐진 트리의 rank가 1 증가한다.
- Union by Size: 트리에 속한 원소 개수(size)를 기준으로, 원소가 적은 트리를 많은 트리 밑에 붙인다. union 이후에는 두 트리의 size를 더해서 갱신한다.
두 방식 모두 목적은 같다. 트리가 한쪽으로 치우쳐서 깊어지는 것을 방지하는 것.
Union by Rank로 구현하면 다음과 같다.
const parent = Array.from({ length: n }, (_, i) => i);
const rank = Array(n).fill(0);
function unionByRank(a, b) {
const rootA = find(a);
const rootB = find(b);
if (rootA === rootB) return; // 이미 같은 집합
// rank가 작은 트리를 rank가 큰 트리 밑에 붙인다
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
} else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
} else {
// rank가 같으면 한쪽을 붙이고, 붙인 쪽의 rank를 1 증가시킨다
parent[rootB] = rootA;
rank[rootA]++;
}
}Path Compression과 Union by Rank(또는 Size)를 함께 사용하면 Find, Union 연산의 시간복잡도는 O(α(N))이 된다. 여기서 α(N)은 아커만 함수의 역함수로, N이 아무리 커져도 실질적으로 4~5를 넘지 않는 값이라 사실상 상수 시간(O(1))으로 취급해도 무방하다.
ㅤ
-
parent배열을 만들어 각 원소를 자기 자신으로 초기화한다. - Find 연산을 수행할 때, 부모를 계속 따라 올라가 루트를 찾는다.
- 루트를 찾는 과정에서 거쳐간 노드들은 경로 압축을 통해 루트에 바로 연결한다.
- Union 연산을 수행할 때, 두 원소의 루트를 각각 찾는다.
- 두 루트가 다르면, 한쪽 루트를 다른 쪽 루트의 자식으로 만들어 집합을 합친다.
- 두 루트가 같으면, 이미 같은 집합이므로 아무것도 하지 않는다.
ㅤ
Union-Find는 다음과 같은 유형의 문제에서 자주 사용된다.
- 연결 여부 확인 문제 두 원소가 같은 집합(같은 네트워크, 같은 그룹)에 속하는지 확인하는 문제
- 그룹(네트워크) 개수 세기 문제 전체 원소가 몇 개의 그룹으로 나뉘는지 구하는 문제
- 사이클 판별 문제 간선을 하나씩 union하면서, 이미 같은 집합인 두 노드를 다시 연결하려고 하면 사이클이 생기는 것으로 판단
- 최소 신장 트리(MST) 문제 크루스칼 알고리즘에서 간선을 정렬한 뒤, Union-Find로 사이클 여부를 확인하며 트리를 구성
ㅤ
🏝️섬 연결하기
섬의 개수 n과, 각 섬을 연결하는 다리 정보가 담긴 2차원 배열 costs([섬1, 섬2, 비용])가 주어질 때, 모든 섬을 연결하는 데 필요한 최소 비용을 구하는 문제
Union-Find / 최소 신장 트리(MST) / 크루스칼
이 문제는 각 섬이 원소이고, 다리를 비용이 작은 순서대로 하나씩 연결(union)해 나가는 크루스칼 알고리즘으로 풀 수 있다. 이때 두 섬이 이미 같은 집합(같은 루트)이라면 연결해도 새로운 섬이 추가되지 않고 사이클만 생기므로, Union-Find로 두 섬의 루트가 같은지 확인해서 이런 경우를 걸러낸다.
Java
import java.util.*;
class Solution {
public int solution(int n, int[][] costs) {
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// 비용이 작은 순서대로 정렬
Arrays.sort(costs, (a, b) -> a[2] - b[2]);
int answer = 0;
for (int[] edge : costs) {
int a = edge[0];
int b = edge[1];
int cost = edge[2];
// 두 섬이 이미 연결되어 있지 않은 경우에만 연결
if (find(parent, a) != find(parent, b)) {
union(parent, a, b);
answer += cost;
}
}
return answer;
}
private int find(int[] parent, int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent, parent[x]); // 경로 압축
}
private void union(int[] parent, int a, int b) {
int rootA = find(parent, a);
int rootB = find(parent, b);
if (rootA != rootB) {
parent[rootB] = rootA;
}
}
}Python
def solution(n, costs):
parent = list(range(n))
def find(x):
if parent[x] == x:
return x
parent[x] = find(parent[x]) # 경로 압축
return parent[x]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a != root_b:
parent[root_b] = root_a
# 비용이 작은 순서대로 정렬
costs.sort(key=lambda x: x[2])
answer = 0
for a, b, cost in costs:
# 두 섬이 이미 연결되어 있지 않은 경우에만 연결
if find(a) != find(b):
union(a, b)
answer += cost
return answerJavaScript
function solution(n, costs) {
const parent = Array.from({ length: n }, (_, i) => i);
// 루트를 찾는 함수 (경로 압축 포함)
function find(x) {
if (parent[x] === x) return x;
return (parent[x] = find(parent[x]));
}
// 두 집합을 합치는 함수
function union(a, b) {
const rootA = find(a);
const rootB = find(b);
if (rootA !== rootB) {
parent[rootB] = rootA;
}
}
// 비용이 작은 순서대로 정렬
costs.sort((x, y) => x[2] - y[2]);
let answer = 0;
for (const [a, b, cost] of costs) {
// 두 섬이 이미 연결되어 있지 않은 경우에만 연결
if (find(a) !== find(b)) {
union(a, b);
answer += cost;
}
}
return answer;
}- 섬 개수만큼
parent배열을 만들어 각 섬을 자기 자신으로 초기화한다. -
costs배열을 비용이 작은 순서대로 정렬한다. (크루스칼 알고리즘의 핵심) - 정렬된 간선을 순서대로 확인하면서, 두 섬의 루트를 find로 찾는다.
- 두 섬의 루트가 다르면 union으로 연결하고, 비용을 answer에 더한다.
- 두 섬의 루트가 같으면 이미 연결된 상태(사이클이 생기는 경우)이므로 건너뛴다.
- 모든 간선을 확인한 뒤 answer를 반환하면, 그 값이 모든 섬을 연결하는 최소 비용이 된다.
ㅤ
1. Find 연산에서 경로 압축을 빼먹는 경우
경로 압축을 하지 않으면 트리가 한쪽으로 길게 늘어져서(편향 트리) 최악의 경우 Find 연산이 O(N)까지 느려질 수 있다.
// 추천: 찾은 루트를 바로 부모로 연결
function find(x) {
if (parent[x] === x) return x;
return (parent[x] = find(parent[x]));
}2. Union 시 루트가 아니라 원소 자체를 연결하는 경우
parent[a] = b처럼 원소를 바로 연결하면 안 되고, 반드시 각 원소의 루트를 find로 찾은 뒤 루트끼리 연결해야 한다.
// 잘못된 예
parent[a] = b;
// 올바른 예
const rootA = find(a);
const rootB = find(b);
if (rootA !== rootB) parent[rootB] = rootA;3. 이미 같은 집합인지 확인하지 않고 union하는 경우
두 원소의 루트가 이미 같은데도 union을 수행하면 불필요한 연산이 발생하고, 사이클 판별 로직에서는 잘못된 결과가 나올 수 있다. 사이클 판별이 필요한 문제(ex. 크루스칼)에서는 rootA === rootB일 때 사이클이 발생한 것으로 처리해야 한다.
4. 배열 크기와 인덱스(0번 사용 여부)를 헷갈리는 경우
문제에서 원소 번호가 1번부터 시작하는지 0번부터 시작하는지에 따라 parent 배열 크기와 초기화 범위가 달라진다. 인덱스 범위를 맞추지 않으면 존재하지 않는 원소를 참조하는 오류가 발생할 수 있다.