분리 집합8 [백준 1717] 집합의 표현 [Java] 풀이 대표적인 Disjoin Set 문제이다. 일전에도 기본 Set이 아닌 Disjoin Set을 이용해 문제를 푼 경험이 있다. [백준 1043] 거짓말 [Python] 풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(peop kyr-db.tistory.com 문제에서 주어진 n + 1개의 집합은 Disjoin Set을 이용할 때 기본적으로 자신의 부모는 자신임을 나타내는 과정이다. 때문에 n + 1의 인덱스에 대해 자신의 인덱스로 초기화를 해주면 된다. 그 이후로는 문제에서 주어진대로 집합 a, b에 대해 입력을 받아 공통 부모를 갱신하거나.. 2023. 6. 28. [백준 1043] 거짓말 [Python] 풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(people)이 또 다른 파티에 참석하게 될 경우 지민이는 마찬가지로 진실만을 말해야 한다. Disjoint Set 구현 풀이 즉, 한 명이라도 진실을 아는 사람이 있는 파티(know_truth)에 참석한 사람들(people)의 Disjoint Set 관계 간 동일 그룹 및 동일 root node를 가지게 되는 것이다. 파티에 참석한 모든 인원을 공통 조상으로 묶어주자. M개의 파티는 진행되는 파티마다 새로 진실을 알게 되는 사람들이(people) 늘어날 수 있으니, 파티를 모두 마친 후 지민이가.. 2023. 4. 23. 이전 1 2 다음
