백준 1717번 집합의 표현 :: 마이구미

이 글은 백준 알고리즘 문제 1717번 "집합의 표현" 을 풀이한다.

문제는 디스조인트-셋(disjoint-set)을 이용하여 해결할 수 있다.

문제 링크 - https://www.acmicpc.net/problem/1717

디스조인트-셋 이해 - http://mygumi.tistory.com/246

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

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

이 문제는 디스조인트-셋에 대해 기초를 다지기 위한 가장 기본적인 문제가 된다.

0일 때, 유니온(union) 을 호출하고, 1일 때, 파인드(find) 를 호출하면 된다.

다음 예제를 통해 확인해보자.

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

0 1 3 => 1, 3을 유니온을 통해 합친 결과는 다음과 같다.

1 1 7 => 1의 부모는 1, 7의 부모는 7이기 때문에 NO

0 7 6 => 7, 6을 합친 결과는 다음과 같다.

1 7 1 => 7의 부모는 1, 1의 부모는 1이기 때문에 NO

0 3 7 => 3, 7을 합친 결과는 다음과 같다.

0 4 2 => 4, 2을 합친 결과는 다음과 같다.

가장 기본적인 문제이기 때문에, 이 문제를 풀고 다른 디스조인트-셋 문제를 풀어보길 바란다.

링크 - 디스조인트-셋 문제 카테고리 

Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/disjoint-set