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

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

1717번: 집합의 표현

 

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

 

시행착오

1. 분리집합 개념을 간단히 이해하고 웃으며 구현했다 -> 시간초과

 return root(par[i]);
 
//⬇️

 return par[i] = root(par[i]);

 모든 노드의 부모 노드가 루트노드가 될 수 있도록 최적화했다.

즉, 루트를 찾으러 가는 재귀함수의 연산 과정에서 루트노드를 부모로 잡을 수 있게 코드를 바꿈

 

2. 근데 또 시간초과가 났다

    cin.tie(0);
    cin.sync_with_stdio(false);
    ios_base::sync_with_stdio(false);

알고리즘 캠프 첫째날 듣고 그동안 잊고있었던 이 코드... 를 추가하니 되었다..

저 의미를 알고싶지도 않아 잊고있었던 코드의 소중함을 깨달았다

 

풀이

분리집합과 관련된 기본 함수를 구현하는 간단한 문제라서 관련 개념만 공부하고도 풀 수 있었다

물론 나는 인터넷의 힘을 빌리긴 했지만 이게 왜 골드인건지.. 의문.....

 

#include <iostream>

using namespace std;

int par[1000001];

//루트노드를 반환해주는 함수
int root(int i){
    if(par[i] == i)
        return i;
    
    return par[i] = root(par[i]);
}

int main() {
    
    cin.tie(0);
    cin.sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    
    //입력 및 세팅
    int n, m;
    cin >> n >> m;
    
    for(int i=0; i<=n; i++){
        par[i] = i;
    }
    
    while(m--) {
        int op, a, b;
        cin >> op >> a >> b;
        
        int A = root(a);
        int B = root(b);
        
        //합집합 연산
        if(op == 0 && A != B){
            par[A] = B;
        }
        
        //포함여부 확인 연산
        else if(op == 1){
            if(A == B)
                cout << "yes\n";
            else
                cout << "no\n";
        }
    }
    
    return 0;
}