[백준 1043번][Python] - 거짓말

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

 

 

 

 

 

 

# 전체탐색 풀이과정

1. 동일한 사람이 진실과 거짓을 모두 들어서는 안됨

2. 진실을 알고있는 사람이 속한 그룹에는 사실만을 말해야함

3. 즉, 진실을 알고있는 사람과 같은 그룹에 속한 모든 사람들도 진실을 알게되는것임

4. 시간제한은 2초, N,M의 범위는 최대 50으로, 모든 그룹을 탐색하기에 충분한 시간임

5. 모든 그룹을 순회하면서 진실을 전파시킴

6. 최종적으로 진실을 모르는 사람들만 있는 그룹의 수를 카운트해서 출력

 

 

[전체탐색을 이용한 코드 - 성공]

# ex_1043
import sys
N, M = map(int, sys.stdin.readline().split())
member = [0 for _ in range(N+1)]  # 멤버(0: 진실을 모름 | 1: 진실을 앎)
l = list(map(int, sys.stdin.readline().split()))
if l[0] == 0:   # 아는 사람이 아무도 없을 경우에는 모든 파티에서 거짓말이 가능
    print(M)
    exit()
else:
    for x in l[1:]:
        member[x] = 1
party = [list(map(int,sys.stdin.readline().split()))[1:] for _ in range(M)]

# 진실 전판 함수
def ext(sub):
    for mem in sub:
        member[mem] = 1

# 진실을 아는 사람과 같은 그룹인 사람들도 진실을 알게됨
for _ in range(M):
    for sub in party:
        for known in sub:
            if member[known] == 1:
                ext(sub)
                break

# 거짓말을 할수있는 파티의 수 계산
cnt = 0
for sub in party:
    for man in sub:
        if member[man] == 1:
            break
    else:
        cnt += 1

print(cnt)

 

set와 union을 이용하면 위의 코드보다 간단하게 변경이 가능할것같다.