[C++] BOJ 1717번 : 집합의 표현

 

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

 

문제 3줄 요약

1. n+1개의 집합이 있다.

2. 합집합 연산과 두 원소가 같은 집합인지 판별하는 연산을 수행한다.

3. 1로 시작하는 입력에 대해서는 포함 여부를 출력한다.

 

---

 

 

문제의 제한 사항을 확인해보면

n은 최대 10^6 이므로 단순히 set를 이용한 집합 연산은 불가능하다고 생각하였다.

 

해당 문제에서는

Disjoint-set(서로소 집합, 분리 집합)을 표현하는 Union-Find 알고리즘을 이용하였다.

 

해당 알고리즘이 익숙하지 않다면

아래 영상을 참고하길 바란다!!

 

https://www.youtube.com/watch?v=rE-OUyZJgOk

 

 

---

 

 

 

 

위와 같은 집합이 존재할 때,

부모 정점 테이블을 이용하여 집합의 연결을 수행한다.

 

연결하고자 하는 두 집합의

번호가 작은 쪽의 부모 정점을 기준으로 테이블 값을 변경하여 연결을 유지한다.

 

위 그림에서 { 1, 2, 3, 5, 6 } 은 연결 상태이다.

그 중 작은 원소가 1이므로

모든 연결이 이루어 질 때, 부모 정점은 모두 1로 통한다.

 

특히 3의 경우

2를 거쳐 1를 통하므로 재귀를 통한 부모 정점 탐색 또한 필요하다.

 

 

즉

1. 더 작은 부모 정점을 기준으로 테이블 값 변경

2. 재귀를 통한 부모 정점 탐색

 

2가지 기능이 집합의 연결에 있어 필요하다.

 

---

 

#include <iostream>

using namespace std;

int nums[1'000'001];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n, m;
    cin >> n >> m;

    for(int i=0; i<=n; i++) nums[i] = i;

    while(m--){
        int a, b, c;
        cin >> a >> b >> c;

        if(a==0) func_union(b, c);
        else if(a==1) func_find(b, c); 
    }

    return 0;
}

 

문제로 돌아가서

0 연산은 합집합 연산 (func_union),

1 연산은 포함 여부를 확인한다 (func_find).

 

합집합 연산부터 구현해보자.

 

앞서 말했듯이 합집합에는 2가지 기능이 필요하다.

 

int func_getParent(int num){
    if(nums[num] == num) return num;
    return nums[num] = func_getParent(nums[num]);
}

void func_union(int b, int c){
    b = func_getParent(b);
    c = func_getParent(c);
    if(b < c) nums[c] = b;
    else nums[b] = c;
}

 

1. 부모 정점을 탐색하는 func_getParent 함수

 

인자로 받은 num이 부모 정점의 테이블인 nums의 값과 동일하다면?

해당 정점이 부모 정점이므로

num (= 부모 정점)을 반환해준다.

 

동일하지 않다면, 우린 재귀를 통해 부모 정점으로 이동해야 한다.

nums[num] 의 값을 재귀로 찾아올 부모 정점 값을 넣어준다.

 

 

2. 부모 정점 값을 변경하는 func_union 함수

 

탐색한 부모 정점을 기준으로

더 작은 쪽으로 부모 정점 테이블을 변경한다.

 

 

void func_find(int b, int c){
    b = func_getParent(b);
    c = func_getParent(c);
    if(b == c) cout << "YES\n";
    else cout << "NO\n";
}

 

3. 부모 정점을 비교하는 func_find 함수

 

확인하고자 하는 두 원소의 부모가 같다면

같은 집합에 속하는 것이다.

 

따라서 부모 정점을 탐색 후 비교해주면 되겠다.

 

 

최종 코드는 아래와 같다.

 

#include <iostream>

using namespace std;

int nums[1'000'001];

int func_getParent(int num){
    if(nums[num] == num) return num;
    return nums[num] = func_getParent(nums[num]);
}

void func_union(int b, int c){
    b = func_getParent(b);
    c = func_getParent(c);
    if(b < c) nums[c] = b;
    else nums[b] = c;
}

void func_find(int b, int c){
    b = func_getParent(b);
    c = func_getParent(c);
    if(b == c) cout << "YES\n";
    else cout << "NO\n";
}

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n, m;
    cin >> n >> m;

    for(int i=0; i<=n; i++) nums[i] = i;

    while(m--){
        int a, b, c;
        cin >> a >> b >> c;

        if(a==0) func_union(b, c);
        else if(a==1) func_find(b, c); 
    }

    return 0;
}

 

---

 

영상을 통해 이론을 익히고 풀어서 어렵진 않았지만

모르고 푼다면 못풀지 않았을까... 싶다.

 

끝!