[BOJ] #1717 - 집합의 표현

👻 집합의 표현

👉🏻 문제 보러가기 👈🏻

---

🌱 문제

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

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

• 시간 제한 : 2초
• 메모리 제한 : 128 MB

---

🌱 입력

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

---

🌱 출력

1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 “YES” 또는 “yes”를, 그렇지 않다면 “NO” 또는 “no”를 한 줄에 하나씩 출력한다.

---

🌱 제한

• 1 ≤ n ≤ 1,000,000
• 1 ≤ m ≤ 100,000
• 0 ≤ a, b ≤ n
• a, b는 정수
• a와 b는 같을 수도 있다.

---

🌱 예제

---

🪐 입출력 1

• 입력

  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
  

---

👻 풀이

#include <iostream>
#include <vector>
using namespace std;

class DisjointSet
{
public:
    DisjointSet(int n) : _parent(n), _rank(n, 0)
    {
        for (int i = 0; i < n; i++)
            _parent[i] = i;
    }

    int Find(int u)
    {
        if (u == _parent[u])
            return u;
        return _parent[u] = Find(_parent[u]);
    }

    void Union(int u, int v)
    {
        u = Find(u);
        v = Find(v);

        if (u == v)
            return;

        if (_rank[u] > _rank[v])
            swap(u, v);
        
        _parent[u] = v;

        if (_rank[u] == _rank[v])
            _rank[v]++;
    }
private:
    vector<int> _parent;
    vector<int> _rank;
};

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// 집합의 표현
    int n, m, a, b, c;
    cin >> n >> m;
    DisjointSet sets(n + 1);
    while (m--)
    {
        cin >> c >> a >> b;
        if (c)
        {
            int u = sets.Find(a);
            int v = sets.Find(b);
            if (u == v)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
        else
        {
            sets.Union(a, b);
        }
    }
    return 0;
}

• 시간 : 40 ms
• 메모리 : 9836 KB

---

👻 글을 마치며

방금 막 최소 스패닝 트리를 공부하고 바로 푼 알고리즘 문제였는데 생각보다 쉽게 풀었던 것 같다. 그래도 아직까지는 안 보고 코드 작성하는 게 95%, 보고 작성하는 부분이 5% 정도 되는 것 같은데, 보고 작성하는 부분이 0% 될 때까지 반복 학습을 해야할 것 같다.

---

소스코드 보러가기