[BOJ] 백준 1717 집합의 표현 c++ (유니온 파인드)

문제 출처 : https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

---

풀이

두 집합 a와 b가 같은 집합에 포함되어 있는지 확인하는 문제이다.

처음에 bfs로 완전탐색으로 구현하였으나, 시간초과가 발생하였다.

따라서 유니온 파인드를 통해 해결해야 한다.

---

처음 모든 수의 부모를 나타내는 배열 parent를 선언한다.

이 parent 배열은 항상 부모중 가장 작은 값을 가진 노드로 갱신해준다.

getParent

부모를 찾아주는 함수로 재귀함수로 구현하였다.

parent[x] = x 인경우 본인이 최소 값 노드이므로 return한다.그렇지 않으면 재귀함수를 실행한다.

int parent[1000000+1];

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

unionParent

가장 작은 부모 노드 값으로 초기화 하는 함수이다.

getParent에서 받아온 값을 비교해 구현한다.

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    // 작은 부모 노드 값으로 초기화
    if(a > b) parent[a] = b;
    else parent[b] = a;
}

findParent

a와 b가 같은 노드에 있는지 확인하는 함수이다.

역시 getParent에서 받아온 값을 비교해 구현한다.

void findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) cout << "YES\n";
    else cout << "NO\n";
}

---

코드(완전탐색, 시간초과)

혹시 몰라 시간초과 코드도 공유한다!

#include <bits/stdc++.h>

using namespace std;

int n, m;

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    vector<int> v[n+1];
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        if(a == 0){
            v[b].push_back(c);
            v[c].push_back(b);
        }
        else if(a == 1){
            queue<int> q;
            vector<bool> check(n+1);
            q.push(b);
            bool flag = false;
            while(!q.empty() && !flag){
                int num = q.front();
                check[num] = true;
                q.pop();
                for(int i = 0; i < v[num].size(); i++){
                    if(v[num][i] == c){
                        cout << "YES" << '\n';
                        flag = true;
                        break;
                    }
                    else if(!check[v[num][i]]){
                        check[v[num][i]] = true;
                        q.push(v[num][i]);
                    }
                }
                if(flag) break;
            }
            if(!flag) cout << "NO" << '\n';
        }
    }
	return 0;
}

코드(유니온 파인드, 정답)

#include <bits/stdc++.h>

using namespace std;

int n, m;
int parent[1000000+1];

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

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    // 작은 부모 노드 값으로 초기화
    if(a > b) parent[a] = b;
    else parent[b] = a;
}

void findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) cout << "YES\n";
    else cout << "NO\n";
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        parent[i] = i;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        if(!a)
            unionParent(b, c);
        else
            findParent(b, c);
    }
	return 0;
}