HwangHub

문제 링크 해석 이 문제는 조합과 그래프 탐색을 조합하여 푸는게 일반적인 방식이다. 하지만 유니온파인드로 풀어보라고 제안을 받아서 이를 이용하여 "부분집합 + 유니온파인드"로 풀었다. 정점의 개수가 N, 간선의 개수가 E라고 할 때, 유니온파인드 시간복잡도가 O(E * log N)이고, 부분집합의 시간복잡도가 선택하냐 마냐이므로 O(2^N)이다. 따라서 내가 구성한 로직은 O(2^N * E) 인데, 10! 이 약 4백만이고, N이 10까지이므로 1초 내로 구성할 수 있을 것으로 판단했다. 풀이 코드가 길고 지저분해서, 만약 코드를 보고자 하는 분은 흐름을 먼저 체크해주시길 바란다. /* * 1. 부분집합을 구한다. * * 2. 구해진 부분집합을 기준으로 선거구로 가능한지 체크한다. * -> adj 리스트..