[C/C++] 백준 #1976 여행 가자(배타적 집합)

이번문제는 도시와 도시간 연결 정보를 알고 있으면, 중간에 다른 도시를 경유해서라도, 원하는 도시들을 여행할 수 있는지를 알아보는 것입니다.

 

Let's go a trip

 

사실 이 문제는 그래프를 만들어서 DFS나 BFS를 통해서 원하는 도시들을 다 방문하는지 찾아보아도 됩니다.

저는 배타적 집합(Disjoint Set)을 이용했습니다.  배타적 집합에서 집합을 찾고 합집합을 하는 것이 모두 상수시간이 걸리기 때문에, 전체적으로 $O(N^2)$의 알고리즘 효율로 할 수 있습니다.

 

연결된 도시가 나타나면, 각각의 도시가 속한 집합을 합집합을 하게 됩니다.  그러면 서로 분리된 한개 이상의 집합들이 나오게 되는데, 여행하고자 하는 도시들이 같은 집합에 있는지 검사하면 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1976 - Let's go a trip
//        - by Aubrey Choi
//        - created at 2019-07-10
//------------------------------------------------
#include <stdio.h>

int getroot(int set[], int n)
{
    if(set[n] == n) return n;
    return set[n] = getroot(set, set[n]);
}

int main()
{
    int n, m, s, set[201] = {0, };
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) set[i] = i;
    for(int i = 1; i <= n; i++)
    {
        int a = getroot(set, i);
        for(int j = 1; j <= n; j++)
        {
            scanf("%d", &s);
            if(j <= i || s == 0) continue;
            int b = getroot(set, j);
            if(a != b) set[b] = a;
        }
    }
    scanf("%d", &s);
    int r = getroot(set, s);
    while(--m)
    {
        scanf("%d", &s);
        if(getroot(set, s) != r) break;
    }
    puts(m ? "NO" : "YES");
}