HwangHub

🤔 Intuition 처음에 완탐인 줄 알았다. N과 M이 50 이하이고 시간제한이 2초 이내라서 거의 확신을 했다. 근데, 일단 TC만 맞고 나서, 제출하니까 3%에서 바로 틀렸다. (실전이였다면 맞았다고 착각해서 틀렸을 확률 99.9%) 진실을 아는 사람들이 있는 파티에 참여하는 사람들도 진실을 알게 되는데, 이게 1다리만 계산하면 되는 게 아니라 엮이는 사람 간의 관계 모양이 skewed tree가 될 경우에는 반복수를 감안할 수 없기 때문에 브루트포스로는 반복수의 기준이 명확하지 않다. 즉, 관계성을 계속 저장해둬야 하는 문제였던 거다. 이는 사람간의 그래프를 형성하는 문제라고 볼 수 있으므로, union find로 풀어낼 수 있다. 🔎 Algorithm & Complexity * @algorit..

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