[백준 1043] 거짓말 - python (solved.ac - 골드 4)

https://www.acmicpc.net/problem/1043

1043번: 거짓말

풀이

문제를 보았을때 알수있는 힌트

문제를 이해하면 쉽게 풀 수 있는 문제입니다.

입력을 통해 총 사람 수 50, 파티 수 50 ,  파티 하나 당 50명씩 있다고 해도 총 50*50 =2500번이 돌아간다.

추가적으로 50번씩 돌리게 해도 총 125000번 돌기에 문제를 통과하기에는 충분한 시간이다.

먼저 진실을 알수밖에 없는 수를 만들면 되는데 처음 2번째 줄에서 나오는 진실의 사람을 체크 한다.

이후 파티에 진실을 아는 사람이 있는지 찾고 있는 경우에 그 파티에 있던 사람들도 진실을 아는 사람으로 추가하면 된다.

이것을 파티가 총 50개이기 때문에 처음부터 50번을 반복해서 돌려준다. 이유는 처음에 통과 과장을 들었을수도 있는 사람이 통과했을수도 있기 때문이다.

이를 고려해서 푸면 충분히 풀 수 있는 문제이다.

왜.. 골드 4인지는 모르지만 아마 유니온 파인드로 풀게 하려는 의도이지만 입력이 작기에 쉽게 반복문만 이용해도 풀수있다.

import sys

input= sys.stdin.readline

n,m = map(int,input().split())

dp = [False for _ in range(m+1)]

truePersonCount = list(map(int,input().split()))
truePerson=set(truePersonCount[1:])
party=[]
count = 0

for i in range(m):
    temp = list(map(int,input().split()))[1:]
    party.append(temp)

for _ in range(50):
    for i in party:
        temp = i
        tempBool = False
        for j in temp:
            if j in truePerson:
                tempBool = True
                break
        if tempBool==True:
            for j in temp:
                truePerson.add(j)
for i in party:
    temp = i
    for j in temp:
        if j in truePerson:
            break
    else:
        count+=1
print(count)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1043.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리