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])); // 경로 압축
}- 두 집합을 합칠 때, 항상 트리의 높이(rank)나 크기(size)가 작은 쪽을 큰 쪽 밑으로 붙이는 최적화 기법
- 이렇게 하면 트리가 한쪽으로 치우쳐서 깊어지는 것을 방지할 수 있다.
- Path Compression과 Union by Rank/Size를 함께 사용하면 Find, Union 연산이 거의 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 배열 크기와 초기화 범위가 달라진다. 인덱스 범위를 맞추지 않으면 존재하지 않는 원소를 참조하는 오류가 발생할 수 있다.