1043 - 거짓말 / gold 4 / set 활용

- 첫 시도 / 틀린 코드

"""
1043 - 거짓말 / gold 4
"""
import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
true_list = list(map(int, input().split()))
true_set = set(true_list[1:])
party_list = deque()
for _ in range(m):
    party_info = list(map(int, input().split()))
    party_list.append(set(party_info[1:]))

count = 0
while party_list:
    party_set = party_list.popleft()
    if true_set & party_set:
        count += 1
        if party_set - true_set:
            true_set.update(party_set - true_set)
            true_set.discard(100)
    else:
        if 100 in party_set:
            pass
        else:
            party_set.add(100)
            party_list.append(party_set)

print(m - count)

 

- 정답 코드

"""
1043 - 거짓말 / gold 4 / set 활용
"""
import sys

input = sys.stdin.readline

# 1. Input
n, m = map(int, input().split())
true_list = list(map(int, input().split()))
true_set = set(true_list[1:])

party_list = []
for _ in range(m):
    party_info = list(map(int, input().split()))
    party_list.append(set(party_info[1:]))

# 2. ture_set / add
for _ in range(m):
    for party_set in party_list:
        if party_set & true_set:
            true_set = true_set.union(party_set)

# 3. count
count = 0
for party_set in party_list:
    if party_set & true_set:
        continue
    count += 1

print(count)

1. Input

- n, m : (진실을 아는 사람 수, 파티 수)

- true_set : (진실을 아는 사람 번호) set로 저장

- party_list : (각 파티에 참여하는 사람들 번호 각 인덱스로 저장) / list 안의 set로 저장

 

2. true_set / add 

- 2중 for문 돌면서, 파티에서 진실을 알게 되는 사람들 true_set에 추가 

 

첫 번째 for 문 : m(파티의 수)만큼 돌기

두 번째 for 문 : party_list 길이 만큼 돌기

 

3. count

- party_list 돌면서, count 

 

 

틀린 코드 피드백

 

틀렸던 코드에서는 파티에서 진실을 알게 되는 사람들 또한 생각해서 코드를 짰지만,

특정 파티에서 true_set 에 들어가지 않는 사람들 발생!

 

EX)

(처음에 진실을 몰랐던 사람) -> (파티에서 진실을 알게 된 사람) 이 있다고 예를 들면, 

 

(파티에서 진실을 알게 된 사람) 또한 전파?가 가능하기에 

 

특정 파티 ( 파티에서 진실을 알게 된 사람 + 진실을 모르는 사람들 ) 가 있으면,

(진실을 모르는 사람들) -> (특정 파티에서 진실을 알게 된 사람) 또한 true_set에 추가 해야 함!

 

즉, true_set 에는 해당 번호의 사람이 들어 간다!

1. 진실을 처음부터 아는 사람

2. 진실을 처음부터 아는 사람으로 인해 / 파티에서 진실을 알게 된 사람

3. 파티에서 진실을 알게 된 사람으로 인해 / 특정 파티에서 진실을 알게 된 사람

... 특정 파티에서 진실을 알게 된 사람으로 인해 / 특정특정 파티에 진실을 알게 된 사람 (반복😜)