1717
-
백준 1717번 집합의 표현 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 22:23
이 글은 백준 알고리즘 문제 1717번 "집합의 표현" 을 풀이한다.문제는 디스조인트-셋(disjoint-set)을 이용하여 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/1717디스조인트-셋 이해 - http://mygumi.tistory.com/246 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 이 문제는 디스조인트-셋에 대해 기초를 다지기 위한 가장 기본적인 문제가 된다.0일 때, 유니온(union) 을 호출하고, 1일 때, 파인드(find) 를 호출하면 된다. 다음 예제를 통해 ..