[C++][집합 / 자료구조] 백준 1717번 풀이 및 설명

Union - Find 알고리듬을 사용하면 쉽게 해결할 수 있는 문제이다.

 

다만 이 문제는 시간 초과가 발생하기 때문에 시간을 줄이기 위해 코드를 완성도 있게 짤 필요가 있다.

 

 

문제

 

 

 

 

 

 

알고리듬

 

① 0 a b 형태로 주어진 경우

 

union을 통해 집합을 합쳐 주면 된다.

 

② 1 a b 형태로 주어진 경우

 

a , b의 find 값이 같다면 YES 출력

다르다면 NO 출력

 

 

위의 과정을 모든 입력값에 대하여 시행 하면 된다.

 

 

시간  단축 방법

 

 

1)  stdio 스트림 과의 동기화 취소

cin.tie(NULL);cout.tie(NULL);
ios_base::sync_with_stdio(false);

 

위의 코드를 추가해 주면 cin , cout이 훨씬 빠르게 돌아간다.

 

 

 

자세한 설명은 아래 글 참고..!

 

2022.07.01 - [c++/백준 문제 풀이] - [C++][코딩테스트] 시간 부족 문제 해결 꿀팁 정리( endl , ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL) )

[C++][코딩테스트] 시간 부족 문제 해결 꿀팁 정리( endl , ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout

 

 

2) find 함수 수정

 

int Set::find(int num){
    if(root[num] == num) return num;

    return find(root[num]);
}

 

 

혹시 find 함수를 이렇게 사용한다면 return 부분을 아래와 같이 수정

 

 

int Set::find(int num){
    if(root[num] == num) return num;

    return root[num]= find(root[num]);
}

 

find를 할 때 root 값을 업데이트 해주기 때문에 속도가 더 빨라짐.

 

 

 

 

 

전체 Code

 

 

#include <iostream>

using namespace std;

class Set{

private :
    int* root;

public :    
    Set(int n){ 
        root = new int[n+1];
        for(int i = 0 ; i < n+1 ; ++i) root[i] = i;     
    }

    ~Set(){ delete[] root; };
    
    int find(int num);
    void union_(int num1 , int num2);
    void check_(int num1, int num2);

};

int Set::find(int num){
    if(root[num] == num) return num;

    return root[num]= find(root[num]);
}

void Set::union_(int num1 , int num2){
    num1 = find(num1);
    num2 = find(num2);

    root[num2] = num1;
}

void Set::check_(int num1 , int num2){
    if(find(num1) == find(num2)) cout << "YES\n";
    else cout << "NO\n";
}

int main(int argc, char** argv){
    
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n , m , a , b , zero_or_one;

    cin >> n >> m ;

    Set set(n);


    for(int i = 0; i < m ; ++i){
        
        cin >> zero_or_one >> a >> b;

        if(zero_or_one == 0) set.union_(a,b);
        else if(zero_or_one == 1) set.check_(a,b);
    
    }

    return 0;
}