15주차

Union-Find

개념

여러 원소들을 몇 개의 그룹(집합)으로 묶어서 관리할 때 사용하는 자료구조
Disjoint Set(서로소 집합)이라고도 부른다.
특정 원소가 어떤 집합에 속하는지, 두 원소가 같은 집합에 속하는지를 빠르게 확인할 수 있다.
트리 구조를 이용해서 각 집합을 표현한다. 같은 트리(같은 루트 노드)에 속한 원소들은 같은 집합이라고 본다.

Union-Find는 크게 두 가지 연산으로 이루어진다.

Find: 특정 원소가 속한 집합의 루트(대표 원소)를 찾는 연산
Union: 두 원소가 속한 집합을 하나로 합치는 연산

✨Union-Find의 기본 아이디어

처음에는 모든 원소가 각자 자기 자신을 부모로 갖는 독립적인 집합이다.
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}

ㅤ

Path Compression (경로 압축)

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 by Rank / Size

두 집합을 합칠 때 무작정 한쪽을 다른 쪽 밑에 붙이면, 운이 나쁜 순서로 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]++;
  }
}

Union by Size는 rank 대신 트리에 속한 원소 개수를 비교한다는 점만 다르고, 구조는 거의 동일하다.

const parent = Array.from({ length: n }, (_, i) => i);
const size = Array(n).fill(1);

function unionBySize(a, b) {
  let rootA = find(a);
  let rootB = find(b);
  if (rootA === rootB) return; // 이미 같은 집합

  // size가 작은 트리를 size가 큰 트리 밑에 붙인다
  if (size[rootA] < size[rootB]) {
    [rootA, rootB] = [rootB, rootA];
  }
  parent[rootB] = rootA;
  size[rootA] += size[rootB]; // 합쳐진 트리의 size 갱신
}

정리하면 최적화 여부에 따라 Find, Union 연산의 시간복잡도는 다음과 같이 달라진다.

아무 최적화도 없는 경우: 최악의 경우 트리가 일렬로 늘어져서 연산당 O(N)
Path Compression만 적용한 경우: 상각(amortized) O(log N)
Union by Rank/Size만 적용한 경우: 트리 높이가 O(log N)으로 제한되어 연산당 O(log N)
둘 다 함께 적용한 경우: O(α(N))

여기서 α(N)은 아커만 함수의 역함수로, N이 아무리 커져도 실질적으로 4~5를 넘지 않는 값이라 사실상 상수 시간(O(1))으로 취급해도 무방하다. 즉 두 최적화를 함께 써야 이론상 최선의 시간복잡도가 나온다.

ㅤ

Union-Find의 기본 흐름

parent 배열을 만들어 각 원소를 자기 자신으로 초기화한다.
Find 연산을 수행할 때, 부모를 계속 따라 올라가 루트를 찾는다.
루트를 찾는 과정에서 거쳐간 노드들은 경로 압축을 통해 루트에 바로 연결한다.
Union 연산을 수행할 때, 두 원소의 루트를 각각 찾는다.
두 루트가 다르면, 한쪽 루트를 다른 쪽 루트의 자식으로 만들어 집합을 합친다.
두 루트가 같으면, 이미 같은 집합이므로 아무것도 하지 않는다.

ㅤ

🔍문제 패턴

Union-Find는 다음과 같은 유형의 문제에서 자주 사용된다.

연결 여부 확인 문제 두 원소가 같은 집합(같은 네트워크, 같은 그룹)에 속하는지 확인하는 문제
그룹(네트워크) 개수 세기 문제 전체 원소가 몇 개의 그룹으로 나뉘는지 구하는 문제
사이클 판별 문제 간선을 하나씩 union하면서, 이미 같은 집합인 두 노드를 다시 연결하려고 하면 사이클이 생기는 것으로 판단
최소 신장 트리(MST) 문제 크루스칼 알고리즘에서 간선을 정렬한 뒤, Union-Find로 사이클 여부를 확인하며 트리를 구성 (ex. 아래 예시 문제 "섬 연결하기")

ㅤ

예시 문제 기반 설명

🏝️섬 연결하기

섬의 개수 n과, 각 섬을 연결하는 다리 정보가 담긴 2차원 배열 costs([섬1, 섬2, 비용])가 주어질 때, 모든 섬을 연결하는 데 필요한 최소 비용을 구하는 문제

Union-Find / 최소 신장 트리(MST) / 크루스칼

이 문제는 각 섬이 원소이고, 다리를 비용이 작은 순서대로 하나씩 연결(union)해 나가는 크루스칼 알고리즘으로 풀 수 있다. 이때 두 섬이 이미 같은 집합(같은 루트)이라면 연결해도 새로운 섬이 추가되지 않고 사이클만 생기므로, Union-Find로 두 섬의 루트가 같은지 확인해서 이런 경우를 걸러낸다.

아래 풀이는 앞서 본 Union by Rank/Size 없이 단순 union만 사용한다. 이 문제는 섬의 개수가 최대 100 정도로 작아서 굳이 rank/size 최적화를 하지 않아도 시간 내에 충분히 풀리기 때문이다. 원소 개수가 훨씬 크거나 find 호출이 매우 많은 문제라면 앞에서 본 것처럼 Union by Rank/Size까지 함께 적용하는 게 안전하다.

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 answer

JavaScript

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 배열 크기와 초기화 범위가 달라진다. 인덱스 범위를 맞추지 않으면 존재하지 않는 원소를 참조하는 오류가 발생할 수 있다.

🏠 메인

Home

📖 기본 코테 개념

Time Complexity

Space Complexity

Big-O Notation

Input Size & Algorithm Complexity

📅 주차별 개념

👥 담당 순서

백현빈 → 강민주 → 조수빈 → 임현빈 → 전병훈 → 이건희

(이후 동일한 순서로 반복)

Uh oh!

15주차

Union-Find

개념

✨Union-Find의 기본 아이디어

Path Compression (경로 압축)

Union by Rank / Size

Union-Find의 기본 흐름

🔍문제 패턴

예시 문제 기반 설명

🏝️섬 연결하기

풀이 방법

실수 포인트

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

🏠 메인

📖 기본 코테 개념

📅 주차별 개념

1 ~ 5주차

6 ~ 10주차

11 ~ 15주차

👥 담당 순서

Clone this wiki locally