[백준]1043 거짓말

파티에 진실을 아는사람이 있으면 진실만을 말해야 한다.

새롭게 진실을 알게 된 사람을 고려해야한다(그사람이 참석하는 다른 파티에서도 진실을 말해야한다)

​

1. 풀이

(1) 그래프 연결

1) 파티를 하나의 노드로 본다.

2) 파티를 두개씩 짝지어서 비교하면서, 한사람 이상을 공유하면 연결한다.

(파티1과 파티2를 비교하여 둘다 참여하는사람이 있으면 연결한다.)

3) 연결이 완료되면 탐색을 시작한다.

(2) 탐색

1) 연결된 노드(파티)들을 탐색한다

2) 연결된 파티들 중 하나의 파티에서라도 진실을 아는사람이 있다면, 연결된 모든 파티에는 진실을 말해야한다

3) 한명도 진실을 아는사람이 없다면 연결된 모든 파티에는 과장을 해도된다.

​

2. 소스코드

from collections import deque

N,M=map(int,input().split())
L=list(map(int,input().split()))
knowSize=L.pop(0)
party=[]
peopleSize=[]
for i in range(M):
    temp=list(map(int, input().split()))
    peopleSize.append(temp.pop(0))
    party.append(temp)


# 중복된사람들 있는 파티들끼리 연결
graph={}
for i in range(M):
    graph[i]=[]
for i in range(M):
    for j in range(i+1,M):
        # 두 파티에 중복된 사람이 있으면 연결
        if set(party[i])&set(party[j]):
            graph[i].append(j)
            graph[j].append(i)
#print(graph)

# 서치
ans=0
visited=[0 for i in range(M)]
for i in range(M):
    if visited[i]==0:
        #print(i,"번파티 탐색시작")
        cnt=1
        canLie=True
        q=deque([i])
        visited[i]=1
        if set(party[i])&set(L):
            canLie=False
        while(q):
            temp=q.popleft()
            for conNode in graph[temp]:
                if not visited[conNode]:
                    #진실아는자가 잇는지
                    if set(party[conNode])&set(L):
                        canLie=False
                    cnt+=1
                    visited[conNode]=1
                    q.append(conNode)
        if canLie:
            #print("이파티그룹은 가능, 파티개수는 : ",cnt)
            ans+=cnt

print(ans)