유니온 파인드 (Union-Find)

유니온 파인드 (Union-Find) 설명:

유니온 파인드(또는 Disjoint Set Union, DSU)는 여러 개의 원소가 존재할 때 이 원소들을 여러 개의 집합으로 나누어 관리하는 알고리즘입니다. 주로 그래프에서 연결된 컴포넌트를 판별하거나, 사이클의 존재 여부를 판별하는 데에 사용됩니다.

기본 연산:

1. Union: 두 원소가 속한 집합을 하나로 합칩니다.
2. Find: 어떤 원소가 속한 집합인지 찾습니다.

이 두 연산을 이용하여 집합의 합집합 및 해당 원소의 대표값(루트 노드)을 효율적으로 찾을 수 있습니다.

유니온 파인드의 구현:

기본적으로 유니온 파인드는 각 원소의 부모를 나타내는 배열을 이용하여 구현됩니다. 처음에는 모든 원소의 부모는 자기 자신입니다.

• Find 연산: 주어진 원소의 루트 노드(대표값)를 찾습니다. 경로 압축 기법을 이용하면 이 연산을 매우 빠르게 수행할 수 있습니다.
• Union 연산: 두 원소의 루트 노드를 찾고, 하나의 루트 노드를 다른 쪽의 자식으로 만듭니다.

자바스크립트로의 간략한 구현 예:

class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size }, (_, index) => index);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]); // 경로 압축
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
        }
    }
}

const uf = new UnionFind(5);
uf.union(1, 2);
uf.union(2, 3);
console.log(uf.find(1) === uf.find(3)); // 출력: true

유니온 파인드는 그래프 문제, 네트워크 연결, 사이클 판별 등 다양한 문제에서 유용하게 사용됩니다.