[백준 파이썬] 1043 거짓말

📌문제 출처

솔브닷 4 클래스
https://www.acmicpc.net/problem/1043

1043번: 거짓말

❓ 문제

 

 

 

📗 풀이 코드

'''
if 진실을 아는 사람이 없다면 -> 모든 파티 참가 가능하므로 return m
for 문 : 진실 아는 사람 딕셔너리에 1로 업데이트
for 문 : 파티 개수만큼 반복 -> 최악의 경우 마지막 확인하는 파티에서부터 한명씩 진실을 아는 사람이 늘어날 수 있음
for 문 : 각 파티별 사람을 한명씩 확인하며 한명이라도 진실을 알 경우 전체 파티원들 진실러로 업데이트
         처음에는 입력값을 받아서 party라는 리스트에 넣어주기
         두번째부터는 입력받은 party라는 리스트에서 참가자리스트 꺼내서 확인
진실을 아는 사람 업데이트가 종료되었다면
for 문 : 각 파티별로 참가자를 확인해서 진실을 아는 사람이 한명이라도 있다면 정답에서 1 빼주기
'''

from collections import defaultdict
input = open('input.txt').readline

def solution():
    n,m = map(int,input().split())
    k,*known = list(map(int,input().split()))
    truman = defaultdict(int) # 모르면 0, 알면 1
    if not k : # 진실러가 없다면
        return m # 모든 파티 참가 가능
    else :
        for i in known :
            truman[i] = 1 # 진실러 업데이트
    party = []
    for t in range(m): # 모든 과정을 파티 수만큼 반복
        if not t : # 첫번째 시도라면
            for _ in range(m): # 모든 파티 확인
                _,*nums = list(map(int,input().split())) # 파티별 사람 리스트
                for i in nums :
                    if truman[i] == 1 : # 파티 중 한명이라도 진실을 알면
                        for j in nums :
                            truman[j] = 1 # 진실러 업데이트
                        break # 아는 사람이 나온 순간 전체 업데이트 후 탈출
                party.append(nums) # 파티별 참여자 업데이트
        else :
            for nums in party: # 모든 파티 확인
                for i in nums :
                    if truman[i] == 1 : # 파티 중 한명이라도 진실을 알면
                        for j in nums :
                            truman[j] = 1 # 진실러 업데이트
                        break # 아는 사람이 나온 순간 전체 업데이트 후 탈출
    # 모든 파티를 확인했다면
    ans = m
    for nums in party :
        for i in nums :
            if truman[i] == 1 : # 진실러가 한명이라도 있으면
                ans -= 1 # 그 파티는 참여 불가
                break # 다음 파티 확인
    return ans

if __name__ == '__main__':
    print(solution())