1043: 거짓말

풀이 시간

• 50m

구현 방식

1. 먼저 각 party마다 입력을 받고 분류를 해준다

• union 함수에서,
  1) a와 b가 모두 진실을 아는 사람이라면 return
  2) a는 진실을 알고, b는 진실을 모른다면 b의 parent를 a로 설정
  3) b는 진실을 알고, a는 진실을 모른다면 a의 parent를 b로 설정
  4) a와 b가 둘 다 진실을 모른다면 그냥 작은 쪽에 union

-> parent 완성. find(x) 값이 truth에 포함된다면 진실을 말해야함

2. 완성된 parent를 기반으로 거짓말이 가능한지 아닌지를 확인해준다

• 다시 party를 순회하면서 한 party 당 find(person)의 결과가 truth 안에 포함되는 경우가 한 번도 없는 경우에 count += 1을 해준다

코드

import sys

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a); b = find(b)

    if a in truth and b in truth:
        return
    
    elif a in truth:
        parent[b] = a

    elif b in truth:
        parent[a] = b

    else:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

N, M = map(int, sys.stdin.readline()[:-1].split())
parent = {i: i for i in range(1, N+1)}
truth = list(map(int, sys.stdin.readline()[:-1].split())); truth = set(truth[1:])

parties = []
for m in range(M): #먼저 분류를 해줌
    party = list(map(int, sys.stdin.readline()[:-1].split()))
    personnel = party[0]; party = party[1:]
    for i in range(personnel - 1):
        union(party[i], party[i+1])

    parties.append(party)

count = 0
for party in parties: #거짓말 가능한지 아닌지 확인
    possible = True
    for i in range(len(party)):
        if find(party[i]) in truth:
            possible = False; break
    if possible: count += 1
print(count)

결과