백준 1717번 집합의 표현 — 유니온 파인드 C++ 풀이

문제

BOJ 1717 - 집합의 표현

0부터 N까지의 원소로 구성된 집합에서, 두 집합을 합치는 연산(0)과 두 원소가 같은 집합에 속하는지 확인하는 연산(1)을 수행하는 문제다.

원소마다 “내 집합의 대표는 누구인가”를 부모 배열에 저장한다고 생각하면 된다. 두 집합을 합칠 때는 대표끼리 연결하고, 같은 집합인지 물으면 두 원소의 최종 대표가 같은지 비교한다. 이 자료구조를 서로소 집합, 또는 Union-Find라고 한다.

경로 압축은 대표를 찾으러 올라가는 중간 원소들이 다음부터 곧바로 최종 대표를 가리키게 만드는 최적화다. 첫 조회는 여러 단계를 거칠 수 있지만 이후 조회는 거의 한 번에 끝난다.

핵심 아이디어

1. Union-Find(서로소 집합) 자료구조를 사용한다.
2. get_parent(x): x의 루트를 찾으면서 경로 압축(Path Compression)을 수행한다.
3. make_union(a, b): 두 집합의 루트를 연결하여 합친다.
4. find_union(a, b): 두 원소의 루트가 같은지 비교한다.

풀이

#include <iostream>

using namespace std;

int arr[1000001];
int N, M;

void init(int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = i;
    }
}

int get_parent(int x) {
    if (arr[x] == x) return x;
    else return arr[x] = get_parent(arr[x]);  // 경로 압축
}

void make_union(int _a, int _b) {
    _a = get_parent(_a);
    _b = get_parent(_b);
    if (_a > _b) arr[_b] = _a;
    else arr[_a] = _b;
}

bool same_set(int _a, int _b) {
    return get_parent(_a) == get_parent(_b);
}

int main() {
    scanf("%d %d", &N, &M);

    init(N + 1);

    for (int i = 0; i < M; i++) {
        int judge, a, b;
        scanf("%d %d %d", &judge, &a, &b);

        if (judge == 0) {
            make_union(a, b);
        } else {
            printf(same_set(a, b) ? "YES\n" : "NO\n");
        }
    }

    return 0;
}

주요 포인트

• 경로 압축(arr[x] = get_parent(arr[x])): find 연산 시 모든 노드가 직접 루트를 가리키게 만들어 이후 조회를 O(1)에 가깝게 만든다.
• 경로 압축 없이 단순히 arr[_a] = arr[_b]만 하면 부모의 부모가 바뀌었을 때 추적이 안 되는 버그가 발생한다.
• scanf/printf를 사용하여 입출력 속도를 확보했다.

복잡도

• 시간: O(M × α(N)) — α는 아커만 함수의 역함수, 사실상 O(1)
• 공간: O(N)

Union-Find는 그래프 연결 요소, MST(크루스칼) 등 다양한 알고리즘의 기반이 되는 핵심 자료구조다.