[C/C++] 백준 #1717 집합의 표현(배타적 집합)

이번 문제는 배타적 집합(disjoint set)의 전형적인 예입니다.

 

배타적 집합이라는 것은 임의의 원소가 어느 하나의 집합에만 속해있는 경우입니다.  어떤 원소도 두개 이상의 집합에 속해있지 않기 때문에 일반적으로 사용하는 집합과는 다릅니다.  달리 말하면 임의의 두개의 다른 집합의 교집합은 항상 공집합이라 할 수 있습니다.

 

아래의 그림과 같이, 왼쪽은 배타적 집합입니다.  두 집합 A, B에 공통된 원소가 존재하지 않습니다.  그에 비해 일반 집합은 공통된 원소가 존재할 수 있습니다.

 

disjoint sets vs. not disjoint sets

 

일번적으로 배타적 집합은 배열을 이용하게 됩니다.  보통은 함수를 이용해서 축약까지 넣는데, 축약을 넣지 않은 상태에서도 테스트가 통과해서 그대로 적용했네요.

 

축약을 사용하는 경우에는 다음과 같이 처리합니다.

int getRoot(int v[], int x)
{
    if(v[x] == x) return x;
    return v[x] = getRoot(v, v[x]);
 }

 

축약을 사용하게 되면, 루트를 찾는 평균시간이 \(O(1)\)로 빠르게 작업을 수 있습니다.   만약 시간초과가 생긴다면 축약 기능을 넣어주어야 합니다.

 

합집합인 경우에는 한쪽 집합의 루트의 값을 다른 집합의 루트의 값으로 지정하면 됩니다.  보통은 랭크(rank)를 정해서 작은 집합이 큰 집합으로 흡수되게 하는 것이 좋습니다.  작은 집합의 원소들은 랭크가 하나 증가하게 되겠죠.  전체적으로는 랭크를 증가시키는 것을 방지하는 것에 목적이 있습니다.  하지만 루트의 값을 찾을 때, 축약을 진행하므로, 랭크를 숫자로 지정하면 됩니다.  A 집합의 원소의 갯수가 n개이고, B 집합의 원소의 갯수가 m개인 경우 A 집합이 B집합에 흡수할 때, 축약을 진행했을 경우 평균 찾는 횟수는 \(\frac{2n-1+m}{n+m}\)이 됩니다.  그래서 \(n \le m\)이 되어야 좋겠지만, 알고리즘 효율 관점에서는 크게 상관은 없습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//    baekjoon #1717
//        - by Aubrey Choi
//        - created at 2019-09-18
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, m, c, a, b, sa, sb;
    static int v[1000001];
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++) v[i]=i;
    while(m--)
    {
        scanf("%d%d%d",&c,&a,&b);
        for(sa = a; v[sa]!=sa;sa=v[sa]) ;
        for(sb = b; v[sb]!=sb;sb=v[sb]) ;
        if(c) puts(sa==sb?"YES":"NO");
        else v[sb]=v[a]=v[b]=sa;
    }
}