[백준] 1043번 - 거짓말 (파이썬)

문제) 백준 - 분리 집합 - 거짓말

-> www.acmicpc.net/problem/1043

1043번: 거짓말

 

분리 집합 문제이므로 set() 자료형을 사용하자. 

진실을 아는 사람(witness_set)의 번호와 각 party마다(parties) 참가자들을 집합 자료형으로 입력받는다. 각 파티들을 순회하면서 witness_set와 party의 교집합(intersection)이 존재하면 party의 모든 참가자들을 witness에 추가한다. 교집합이 존재하지 않을 경우 과장된 이야기를 할 수 있는 파티의 개수를 하나 늘린다.

 

 

 

반성)

1. 분리 집합 문제라 생각해서 Union-Find로 구현해서 풀려했다. 코드의 길이가 길어지고 복잡해져 간단한 집합 문제는 set()지료형을 이용해 충분히 풀이가 가능하다.

2. set() 관련 메서드의 이용의 부족. intersection(), union(), difference(), add(), update(), remove() 등 유용하게 쓸 수 있는 메서드들이 많으므로 적극적으로 이용하자.

3. 입력에서 필요한 값만 받기. 이것 때문에 틀린 문제는 아니지만, 코드가 지저분해지는 것을 방지할 수 있다.

 

 

 

소스 코드)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
witness_set = set(input().rstrip().split()[1:])

parties = []
res = []

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


for _ in range(m):
    for i, party in enumerate(parties):
        if witness_set & party:
            res[i] = 0
            witness_set = witness_set | party

print(sum(res))