BOJ 1717 집합의 표현(C++)

집합의 표현 성공 스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3363	978	614	26.707%

문제

초기에 {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

힌트

출처

• 잘못된 데이터를 찾은 사람: Apple_Cplus
• 문제를 번역한 사람: author5

알고리즘 분류

• Disjoint-set

#include    <stdio.h>
#include    <iostream>
#pragma warning(disable : 4996)
int parent[1111111];
int rank[1111111];
struct set {
    set(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            parent[i] = i; //각각 root가 다음
            rank[i] = 1;
        }
    }
    int find(int u)
    {
        if (u == parent[u]) return u;
        return parent[u] = find(parent[u]); //부모의부모의부모의부모
    }
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
 
        if (u == v) //이미 같은부모를 바라보면 상관없음
            return;
 
        if (rank[u] > rank[v])
            std::swap(u, v);
 
        parent[u] = v;
        if (rank[u] == rank[v])
            ++rank[v];
    }
};
 
int main()
{
    int N, M;
    scanf("%d %d,", &N, &M);
    set s(N);
 
    int op, oper1, oper2;
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d", &op, &oper1, &oper2);
 
        if (op == 0) //합연산
        {
            s.merge(oper1, oper2);
        }
        else
        {
            if (s.find(oper1) == s.find(oper2))
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
 
    return 0;
}

처음에는 간단한 문제라고 생각했다. 

각각의 수가 각각의 집합을 가지고 있다면

수    : 0 1 2 3 4 5 6 7

집합 : 0 1 2 3 4 5 6 7

일떄 

2와 4를 묶으면

수    : 0 1 2 3 4 5 6 7

집합 : 0 1 2 3 2 5 6 7

앞의 수인 2의 집합번호인 2를 4의 집합번호로 바꿔준다. 

3과 4를 묶으면

수    : 0 1 2 3 4 5 6 7

집합 : 0 1 3 3 3 5 6 7

이런 방법으로 앞의 수의 집합번호가 3이라면 뒤에 수의 집합번호는 2이므로 집합이 2인 모든 집합의 번호를 3으로 바꿔주면 된다. 

하지만 이럴 경우 1,000,000개의 집합이 있고, 최대 100,000번의 집합연산이 있을 수 있고 최악의경우 

1000000 * 100000번의 연산이라고 한다면 10^11번의 연산이 일어날 수 있으므로 1억회의 연산당 1초라고 했을 때 

문제의 제한인 2초는 당연히 넘을 수 밖에 없다. 

여기서 새로운 풀이방법을 알게 되었는데, Disjoint Set(분리집합)라는 것이다. 

이것을 표현하는 자료구조가 Union Find라고 한다. 

교집합이 없는 분리집합이 있을 때 Union(합집합 연산) , Find(어떤 집합인지 찾는 연산) 을 한다고 하여 붙여진 이름이라고 한다. 

구현을 간단히 설명하면 트리를 사용하여 구현하고, root node는 자신을 가리킨다. 

모든 집합의 번호는 집합이 속한 root node의 번호와 같다. 

이렇게 된다면 Union연산이 획기적으로 줄어들게 된다. 두 집합을 합칠 때 한쪽의 root node를 다른쪽에 붙이면 된다. 

Find또한 root node가 될 때 까지 부모를 찾아 올라가면 된다. 

하지만 이 경우 최악의 경우 한쪽으로 치우친 모양의 트리가 될 수도 있으므로 

rank라는 간단한 시스템?(변수)을 도입함으로써 해결한다. 

rank는 해당 트리의 높이를 저장하고, Union할 때 rank가 낮은 트리를 rank가 높은 트리에 붙이면 이런 문제가 사라진다.