1717 집합의 표현

1717 집합의 표현 (c++)

문제

https://www.acmicpc.net/problem/1717

접근 방식

Union Find

1. 초기에 {0}, {1}, .. , {n} 까지 n + 1 개의 집합이 있음
2. 연산이 주어짐
   1. 두 집합의 합집합 연산
   2. 두 집합이 서로 포함관계인지 확인하는 연산
3. 1번과 2번이 주어지면 Union Find 알고리즘이라는걸 파악해야한다.

문제 풀이

#include <iostream>
#define endl '\n'
#define MAX 1'000'001
using namespace std;

int p[MAX];
int Find(int x) {
    if (p[x] == x) return x;
    return p[x] = Find(p[x]);
}
void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) return;
    else if (a < b) p[b] = a;
    else p[a] = b;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N, M; cin >> N >> M;
    for (int i = 1; i <= N; ++i) p[i] = i;
    int A, B, C;
    while (M-- > 0) {
        cin >> A >> B >> C;
        if (A) { if (Find(B) == Find(C)) cout << "YES" << endl; else cout << "NO" << endl; }
        else Union(B, C);
    }
}

다시 생각해볼 점

1. Union (합집합) 연산에서 세부조건을 걸어야 더 빨라진다는걸 알게 되었다.
   1. a == b 일때 (루트가 같을 때) 이미 포함 관계이므로 합집합 연산 필요 X
   2. a < b 일 때 (a의 루트가 더 작을 때) p[b] = a (b의 루트를 a로 설정)
   3. b < a 일 때 (b의 루트가 더 작을 때) p[a] = b (a의 루트를 b로 설정)
2. Find (탐색) 연산에서도 세부조건을 걸어야 더 빨라진다는 걸 알게 되었다. (최적화)

    return p[x] = Find(p[x]); // p[x]의 값을 Find한 값으로 넣어주면서 반환한다. 이러면 루트노드까지의 탐색 거리가 짧아짐