[BOJ 1043][백준 1043] 거짓말 (파이썬 풀이)

https://www.acmicpc.net/problem/1043

🤔 문제 설명 및 입출력

---

 

✍ 접근 방법

---

생각보다 고려해야할 사항이 많은 문제이다. 단순히 진실을 아는 사람이 있는 파티에서 거짓말을 안하는게 아니라, 진실이 아는 사람이 있던 파티에 있던 사람이 있는 파티에서도 거짓말을 하면 안된다.

 

그럼, 진실을 알고 있는 사람의 목록(이하 진알목) 이 지민이가 하나의 파티를 갈때마다 계속 업데이트가 되는 것이다.

하지만 여기서 문제가 발생하는게, 진알목이 업데이트 되었을때, 이전에 진알목에 따라 구라를 말했던 파티에서도 진실을 말해야하게 된다.

 

그렇다면, 지민이가 한번 파티에 갈 때마다 모든 파티 리스트를 쭉 살펴본 다음, 파티의 멤버와 진알목이 서로 공통분모를 가지고 있나 확인 한 다음, 공통분모를 가지고 있다면, 해당 파티를 진실을 말해야하는 파티로 표시하고 진알목을 업데이트하는 과정을 가져야겠다.

 

이를 코드로 구현해보자. 앞서 말했다시피 "공통분모"라는 개념을 사용해야한다. 집합 자료형의 intersection과 union을 사용하면 훨씬 편리할 것 같다는 생각이 든다.

 

 

👨‍💻 소스 코드

---

• 파이썬

# 1043번 거짓말 : https://www.acmicpc.net/problem/1043

# 기본 아이디어 : 파티 한번 참석할때마다, 남은 모든 파티를 봐서, 지금 진실을 알게 될 사람이 이 자리에 있는지를 확인
# 1. 입력 받는다
# 2. 진실 알고 있는 사람을 집합으로 만듬
# 3. 파티를 순회하면서, 지금 파티에 진실을 아는 사람이 있는지 확인
# 3.1 있다면, 해당 파티를 진실 파티로 마크, 그리고 진실을 아는 사람 set 업데이트
# 3.2 없다면 일단 계속 순회
# 4. 순회가 종료되었을때, 진실 파티의 갯수 파악해서, 구라 파티가 몇개인지 확인한다.

# N,M 모두가 50 이하이므로 복잡도 계산 안해도 된다.

import sys
input = sys.stdin.readline

# N : 사람의 수 ,  M : 파티의 수
N, M = map(int,input().split())
know_truth = set(list(map(int,input().split()))[1:])


parties = []
for _ in range(M):
    party_member = list(map(int,input().split()))[1:]
    parties.append(party_member)

truth_party = [0] * M


for _ in range(M): # 파티 수만큼 반복해라.
    for idx, party in enumerate(parties):
        if know_truth.intersection(set(party)):
            # 여기는 이제 진실을 아는 사람들이 있는 파티니까...표시해야겠지
            truth_party[idx] = 1
            know_truth = know_truth.union(set(party))

print(truth_party.count(0))

 

 

🔥 강평

---

비용이 많이 드는 메서드들을 잔뜩 사용했는데도, 시간초과나 메모리초과 없이 잘 풀었다.

N,M이 작은 값이여서 문제가 없었던게 아닐까 생각이 든다.

만약 N,M이 정말 큰 값이였으면 어떻게 풀어야할지도 고민을 해봐야겠다.