[Python] 백준 1043번 : 거짓말 (빅뱅 거짓말 아님ㅋ)

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

1043번: 거짓말

---

💡 문제 풀이

분리 집합 문제이다.

 

사실 유니온&파인드 알고리즘으로 해결하고 싶었는데 자료구조로 푸는 게 더 적절해 보였다.

진실을 알고 있는 사람들과 각 파티에 참석하는 사람들을 입력받은 다음에 처리를 해줘야 한다.

 

이 문제에서 가장 중요한 것은 이미 거짓말을 들은 사람이 다른 파티에서 진실을 알고 있는 사람과 만날 경우이다.

따라서 진실을 알고있는 사람과 같이 있는 모든 사람들을 진실을 알고있는 그룹에 넣어 최신화를 해줘야 한다.

그 이후 해당 파티에 아무도 알고 있는 사람이 없다면 카운트해준다.

✔️ 느낀 점

유니온 파인드로 해결하려고 했는데 자료구조로 적당한 문제 같아서 한번 풀어봤다.

💻 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
whoKnows = set(input().split()[1:])
parties = []
ans = 0

for _ in range(m):
    parties.append(set(input().split()[1:]))

for _ in range(m):
    for party in parties:
        if party & whoKnows:
            whoKnows = whoKnows.union(party)

for party in parties:
    if party & whoKnows:
        continue
    ans += 1

print(ans)