풀이
N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다.
이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(people)이 또 다른 파티에 참석하게 될 경우 지민이는 마찬가지로 진실만을 말해야 한다.
Disjoint Set 구현 풀이
즉, 한 명이라도 진실을 아는 사람이 있는 파티(know_truth)에 참석한 사람들(people)의 Disjoint Set 관계 간 동일 그룹 및 동일 root node를 가지게 되는 것이다.
파티에 참석한 모든 인원을 공통 조상으로 묶어주자.
M개의 파티는 진행되는 파티마다 새로 진실을 알게 되는 사람들이(people) 늘어날 수 있으니, 파티를 모두 마친 후 지민이가 과장된 이야기를 할 수 있는 파티인지 판별해 주자.
하나의 파티(party)의 모든 인원은 결국 공통 조상을 가지기에 파티 구성원 중 아무나 진실을 아는 사람들의 집합과 비교해 하나라도 동일한 공통 조상을 가지면, 그 그룹은 지민이가 과장된 이야기를 할 수 없는 그룹이다.
Python Set 이용 풀이
위의 풀이처럼 Disjoint Set를 직접 구현해 풀이해도 되지만, Python에는 Set을 기본 제공하기에 아래와 같이 풀이할 수 있다.
기본 로직은 위와 동일하다.
집합 연산을 이용할 수 있게 set으로 저장해주자.
입력받은 M개의 파티에 참석한 인원들에 대해 진실을 알고 있는 사람(know_truth)이 있으면 union으로 묶어주었다.
그룹화된 파티 참석 인원들에 대해 진실을 알고 있는 그룹과 공통 조상을 가지는지 확인해 주자.
높은 레벨의 문제를 갈수록 아무리 Python에서 내장 기능을 지원한다 한들, 직접 구현하고 조건에 맞게 변형해서 이용해야 한다. 기회가 된다면 Disjoin Set도 익혀두자.
(Set을 이용한 풀이 방식에서 데이터를 다룰 때 String이 아닌, Integer로 다루면, 동일한 메모리 사용량이 나올 것이다.)
소스코드
출처
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 1967] 트리의 지름 [Python] (0) | 2023.04.25 |
|---|---|
| [백준 15372] A Simple Problem [Python] (0) | 2023.04.25 |
| [백준 6064] 카잉 달력 [Python] (0) | 2023.04.22 |
| [백준 16928] 뱀과 사다리 게임 [Python] (0) | 2023.04.21 |
| [백준 10188] Quadrilateral [Python] (0) | 2023.04.20 |