알고리즘 스터디 - 백준 1043번 : 거짓말

문제 해석

지민이가 거짓말쟁이로 되지 않고 과장된 이야기를 할 수 있는 파티의 개수의 최댓값을 출력하기

거짓말이 되는 조건

1. 참여하는 모임에 진실을 아는 사람이 있을 때
2. 진실을 아는 모임에 참여하고 진실을 모르는 파티에도 참여하는 진실을 모르는 사람이 있을 때

입력

1. 사람의 수 N, 파티의 수 M
2. 진실을 아는 사람의 수 A, 진실을 아는 사람의 번호 []
3. 파티에 오는 사람의 수 P, 파티 모임에 참가하는 사람의 번호 []

• 입력을 받는 과정에서 진실된 모임에 참여한 사람 & 과장된 모임에 참여한 사람 겹치는 파티를 제외하면 되지 않을까 싶다.

알고리즘 코드

예제 케이스는 다 통과했는데 틀린 알고리즘

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
truth = list(map(int, input().split()))
party = []
count = 0

if truth[0] == 0:
    for _ in range(M):
        non_use = list(map(int, input().split()))
    print(M)
elif truth[0] > 0:
    truth_participant = set(truth[1:])
    truth_party_but_false_participant = set()

    for _ in range(M):
        participant = list(map(int, input().split()))
        set_participant = set(participant[1:])
        # 진실된 사람이 있는 경우
        if len(truth_participant & set_participant) > 0:
            # 진실 이야기를 이미 들은 사람들을 더해줌
            truth_participant.update(set_participant)
        # 없는 경우
        else:
            party.append(set_participant)
            
    # 나중에 다시 재탐색 진행
    print(len([i for i in party if len(i & truth_participant) == 0]))

• 이 코드는 알고리즘을 사용하기 보다 조합+구현을 통해서 겹쳐지는 요소가 존재하는지 최소한으로 가져오는 경우이다. 근데 실제로 돌렸을 때는 틀린 결과가 나왔다. 어떤 반례가 있을까?

최종적으로 맞는 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
truth = list(map(int, input().split()))
party = []

if truth[0] == 0:
    for _ in range(M):
        non_use = list(map(int, input().split()))
    print(M)
elif truth[0] > 0:
    truth_participant = set(truth[1:])

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

    for _ in range(M):
        for i, party_ in enumerate(party):
            if truth_participant.intersection(party_):
                truth_participant = truth_participant.union(party_)
    
    print(len([i for i in party if not truth_participant.intersection(i)]))

여기서 각 for문을 여러번 돌려서 교차점을 체크해주지 않았기에 아까는 틀리고 지금은 맞게 되었다.