글을 시작하며

알고리즘 문제를 풀다 보면 '서로 다른 두 집합을 합치거나(Union)', '특정 원소가 어떤 집합에 속해있는지 찾아야(Find)' 하는 상황을 자주 마주치게 됩니다. 특히 네트워크 연결 상태 확인, 사이클 판별, 최소 신장 트리(MST) 구현 등에서 이러한 연산이 필수적입니다. 따라서 이런 작업을 효율적으로 처리할 수 있는 Union-Find 알고리즘에 대해 자세히 알아보려합니다.

Union-Find 알고리즘

Union-Find(또는 Disjoint Set)는 서로소 집합(Disjoint Set)을 표현하고 관리하는 자료구조입니다.

주요 연산은 아래와 같습니다.

• Initialization(초기화): 각 원소를 개별적인 집합으로 만듭니다.

• Find(찾기): 특정 원소가 속한 집합의 부모(루트)를 찾습니다.

• Union(합치기): 두 개의 집합을 한쪽으로 합칩니다.

최적화 기법

• 경로 압축(Path Compression): find 연산 수행 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸는 방법입니다.

• 랭크 기반 합치기(Union by Rank): 트리의 높이가 낮은 집합을 높은 집합 아래에 합쳐 균형을 유지하는 방법입니다.

find 연산 시 경로 압축을 적용하지 않으면 최악의 경우 O(N) 시간이 걸립니다.

JavaScript로 Union-Find 구현하기

const parents = new Array(N + 1).fill(0);

// 각 노드가 각각의 집합에 포함되도록 초기화
const init = () => {
  for (let i = 0; i <= N; i++) {
    parents[i] = i;
  }
};

// 특정 노드의 부모 노드를 찾음 (해당 노드가 속한 집합의 루트 반환)
const find = (a) => {
  if (a === parents[a]) return a;
  else {
    const b = find(parents[a]);
    parents[a] = b; // 경로 압축 (Path Compression)
    return b;
  }
};

// 두 노드 a, b를 합침
const union = (a, b) => {
  let aRoot = find(a);
  let bRoot = find(b);

  if (aRoot === bRoot) return false;

  parents[bRoot] = aRoot;
  return true;
};

적용할 수 있는 문제

• 크루스칼 알고리즘(Kruskal Algorithm): 최소 신장 트리(MST)를 찾을 때 활용
• 백준 1717: 집합의 표현
• 백준 1976: 여행 가자

주의할 점

• 초기화 잊지 않기: 모든 원소는 처음에 자신이 루트 노드여야 합니다.
• 경로 압축의 중요성: find 연산 시 경로 압축을 적용하지 않으면 최악의 경우 O(N) 시간이 걸립니다.
• union 연산 전 find 호출: 두 원소의 루트를 반드시 찾고 나서 합치기를 수행해야 합니다.

결론

Union-Find는 구현이 비교적 간단하면서도 강력한 알고리즘입니다. 경로 압축과 랭크 기반 합치기 기법을 활용하면 매우 빠른 성능을 유지할 수 있습니다.
특히 그래프 관련 문제에서 자주 활용하며, 코딩 테스트에서도 자주 등장하는 유형이므로 꼭 알아 두어야 하는 알고리즘입니다.

이제 직접 Union-Find를 구현해 보면서 개념을 더 깊이 이해해 보세요! 🚀