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])); // 경로 압축
}

Union by Rank / Size

• 두 집합을 합칠 때, 항상 트리의 높이(rank)나 크기(size)가 작은 쪽을 큰 쪽 밑으로 붙이는 최적화 기법
• 이렇게 하면 트리가 한쪽으로 치우쳐서 깊어지는 것을 방지할 수 있다.
• Path Compression과 Union by Rank/Size를 함께 사용하면 Find, Union 연산이 거의 O(1)에 가까운 시간복잡도를 갖는다.

ㅤ

Union-Find의 기본 흐름

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

ㅤ

문제 패턴

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

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

ㅤ

예시 문제 기반 설명

네트워크

컴퓨터 개수 n과 컴퓨터 간 연결 정보가 담긴 2차원 배열 computers가 주어질 때, 서로 연결되어 있는 컴퓨터의 집합(네트워크)이 몇 개인지 구하는 문제

Union-Find / 그룹 개수 세기

이 문제는 컴퓨터 하나하나가 원소이고, computers[i][j] === 1이면 i번과 j번 컴퓨터가 연결되어 있다는 뜻이다. 연결된 컴퓨터끼리 union을 수행한 뒤, 최종적으로 루트가 서로 다른 개수를 세면 그것이 곧 네트워크의 개수가 된다.

Java

class Solution {
    public int solution(int n, int[][] computers) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (computers[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            if (find(parent, i) == i) {
                answer++;
            }
        }
        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, computers):
    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

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                union(i, j)

    answer = 0
    for i in range(n):
        if find(i) == i:
            answer += 1
    return answer

JavaScript

function solution(n, computers) {
  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;
    }
  }

  // 연결된 컴퓨터끼리 union 수행
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (computers[i][j] === 1) {
        union(i, j);
      }
    }
  }

  // 루트가 자기 자신인 원소의 개수 = 네트워크 개수
  let answer = 0;
  for (let i = 0; i < n; i++) {
    if (find(i) === i) {
      answer++;
    }
  }
  return answer;
}

풀이 방법

1. 컴퓨터 개수만큼 parent 배열을 만들어 각 컴퓨터를 자기 자신으로 초기화한다.
2. computers 배열을 순회하면서, 연결된 두 컴퓨터(i, j)가 있으면 union을 수행한다.
3. union 수행 시, 두 컴퓨터의 루트를 각각 find로 찾는다.
4. 루트가 다르면 한쪽 루트를 다른 쪽 루트에 연결해서 같은 집합으로 만든다.
5. 모든 연결 정보를 처리한 뒤, 전체 컴퓨터를 순회하며 루트가 자기 자신인 컴퓨터의 개수를 센다.
6. 이 개수가 곧 서로 다른 네트워크의 개수가 된다.

ㅤ

실수 포인트

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