[BaekJoon 1717번] 집합의 표현(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

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 를 출력해도 된다)

 

 

[입출력 예]

 

 

입력	출력
7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1	NO NO YES

 

 

[문제 풀이]

 

 

Union-Find 알고리즘 문제이다.

관련 내용은 아래 포스트에 설명해두었다.

[Algorithm] 유니온 파인드(Union-Find)

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

#include <bits/stdc++.h>
using namespace std;
vector<int> parent;

int getParent(int a) {
    if(parent[a] == a) return a;
    else return parent[a] = getParent(parent[a]);
}


void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a == b) return;

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

bool isSameParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i <= n; ++i) {
        parent.emplace_back(i);
    }

    for(int i = 0; i < m; ++i) {
        int z, a, b; // z : 0 이면 합집합 연산, 1이면 같은 집합인지 확인
        cin >> z >> a >> b;
        if(z == 0) {
            // 합집합 Union
            unionParent(a, b);
        } else {
            // 같은 그래프 확인 Find
            if(isSameParent(a, b)) {
                cout << "YES" << '\n';
            } else {
                cout << "NO" << '\n';
            }
        }
    }
    return 0;
}