C++ 코딩테스트 강좌, 유니온 파인드

알고리즘 문제 해결에 있어 유니온-파인드(Union-Find) 자료구조는 매우 유용합니다. 이 글에서는 유니온-파인드의 개념과 C++을 사용한 문제 풀이 과정을 상세히 설명하겠습니다.

유니온 파인드란?

유니온 파인드 유니온-파인드(Union-Find) 알고리즘은 데이터의 집합을 효율적으로 관리하는 자료구조입니다. 이 자료구조는 서로소 집합(Disjoint Set)으로도 알려져 있으며, 주로 다음 두 가지 연산을 지원합니다:

Find: 특정 원소가 어떤 집합에 속하는지를 찾는 연산입니다. 이 연산은 집합의 대표 원소(루트 노드)를 반환합니다.
Union: 두 개의 집합을 통합하는 연산입니다. 이 연산은 두 집합의 루트 노드를 연결하여 하나의 집합으로 만듭니다.

주로 그래프 이론에서 사이클을 찾거나, 연결 요소를 검사하는 문제에서 많이 사용됩니다. 유니온 파인드를 효과적으로 활용하기 위해 두 가지 최적화 기법이 있습니다:

1. 경로 압축(Path Compression)

Find 연산을 수행할 때, 경로를 따라 모든 노드의 부모를 루트 노드로 업데이트하여, 다음 번에 보다 빠르게 루트 노드를 찾을 수 있도록 합니다.

2. 랭크 기반 유니온(Rank-based Union)

Union 연산을 수행할 때, 두 집합의 크기를 비교하여 더 작은 집합을 더 큰 집합의 자식으로 연결합니다. 이렇게 하면 트리의 높이를 줄일 수 있습니다.

문제 설명

이제 유니온-파인드 알고리즘을 사용하여 해결할 수 있는 문제를 보겠습니다. 아래의 문제를 풀어보겠습니다.

문제: 친구 네트워크

여러 친구들이 서로 연결되어 있는 친구 네트워크가 있습니다. 각 친구는 1에서 N까지의 번호로 식별됩니다. 두 친구가 서로 친구라고 불리려면 그들은 직접적인 친구이거나 간접적으로 친구가 되어야 합니다. 당신에게 주어진 친구의 쌍 (a, b)가 있을 때, 친구 네트워크에서 a와 b가 같은 친구 그룹에 속하는지 확인하시오.

입력 형식

첫째 줄에 친구의 수 N과 친구 관계의 수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
둘째 줄부터 M개의 줄에 걸쳐 친구 관계 a, b 의 쌍이 주어진다.
마지막 줄에는 쿼리 Q가 들어오며, 각 쿼리에는 친구 쌍 그들 (x, y)가 주어진다.

출력 형식

각 쿼리에 대해, x와 y가 같은 친구 그룹에 속하면 ‘YES’, 그렇지 않으면 ‘NO’를 출력하시오.

알고리즘 접근 방법

유니온-파인드를 사용하여 친구 관계를 초기화하고 연결합니다. Union(a, b) 를 사용하여 a와 b를 같은 집합으로 연결합니다.
쿼리에 대해 Find(x)와 Find(y)를 사용하여 두 친구의 루트 노드를 확인합니다. 둘이 동일한 루트 노드를 가지면 ‘YES’, 그렇지 않으면 ‘NO’를 출력합니다.

C++ 코드 구현

아래는 유니온-파인드 알고리즘을 구현한 C++ 코드입니다:


#include 
#include 
using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

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

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 랭크 기반 유니온
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector parent;
    vector rank;
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        uf.unionSets(a, b);
    }

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        if (uf.find(x) == uf.find(y)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

코드 설명

위의 C++ 코드에서 우리는 다음과 같은 구성 요소를 구현하였습니다:

UnionFind 클래스: 유니온-파인드 알고리즘의 주요 로직을 포함하고 있습니다. find 함수는 루트 노드를 찾고, unionSets 함수는 두 집합을 통합합니다.
메인 함수: 친구 관계를 입력 받아 유니온-파인드 구조에 저장하고 주어진 쿼리에 대한 결과를 출력합니다.

시간 복잡도

유니온-파인드 알고리즘의 시간 복잡도는 다음과 같습니다:

Find 연산: 거의 상수 시간 (α(N), 아커만 함수의 역함수에 비례)
Union 연산: 거의 상수 시간

따라서 전체 알고리즘의 시간 복잡도는 O(M * α(N)) 입니다. 여기서 M은 친구 관계의 수입니다.

결론

이번 강좌에서는 유니온-파인드 자료구조의 개념과 C++을 활용한 문제 풀이 과정을 자세히 살펴보았습니다. 유니온-파인드는 다양한 문제에서 효과적으로 활용될 수 있는 강력한 도구입니다. 앞으로의 코딩 테스트에서 많은 도움이 되기를 바랍니다.