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

문제

1043번: 거짓말

알고리즘

- set() 자료형을 통해 진실을 아는 사람과 파티에 참여하는 사람을 입력받는다.

- 파티의 수만큼 반복하여 파티에서 진실을 아는 사람이 포함되어 있는 파티를 찾는다. 파티의 수만큼 반복하는 이유는 모든 파티를 확인 후 진실을 아는 사람이 더 생길 경우 모든 파티를 한번 더 확인해줘야 하기 때문이다. 따라서 최대 파티의 수만큼 반복하여 진실을 아는 사람을 찾아야 한다.

- 반복문을 통해 각 파티의 참여한 사람을 확인하고 파티의 참여한 사람 중 진실을 아는 사람이 있는지 확인한다.

- 현재 파티에 진실을 아는 사람이 있다면 현재 파티에서는 진실을 말해야 하고 진실을 아는 사람의 집합에 현재 파티의 사람들을 추가한다.

- 모든 반복이 끝난 후 과장된 이야기를 해도 되는 파티의 수를 출력한다.

코드

import sys

n, m = map(int, sys.stdin.readline().split())
true_n = set(map(int, sys.stdin.readline().split()[1:])) # 진실을 아는 사람

# set() 자료형을 통해 파티에 참여하는 사람의 번호를 입력 받는다.
party = []
for _ in range(m):
    party.append(set(map(int, sys.stdin.readline().split()[1:])))

# 파티의 수, False : 과장된 이야기, True : 진실된 이야기
cnt = [False] * m

# 파티의 수만큼 반복하여 파티에서 진실을 아는 사람이 포합되어 있는 파티를 찾는다.
for _ in range(m):
    # 각 파티에 참여한 사람을 확인
    for i, a in enumerate(party):
        # 현재 파티에 참여한 사람과 진실을 아는 사람의 교집합이 있으면
        if true_n & a:
            cnt[i] = True # 현재 파티에서는 진실을 말해야 한다.
            true_n = true_n | a # 진실을 아는 사람을 추가해준다.

print(cnt.count(False)) # 과장된 이야기를 할 수 있는 파티의 수

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법