1043 백준 파이썬

DFS로 해결했다.

p라는 리스트에 진실을 아는 사람 번호를 넣는다.

stack에 p리스트를 복사해서 넣는다.

p배열에 있는 값들의 vis값을 1로 바꿔주고, stack에서 하나씩 꺼내어 party 리스트의 한줄씩 골라 비교한다.

비교했을때, party 리스트의 한 줄 안에 stack에서 꺼낸 값이 있으면, stack에 party리스트 안의 값(r)을 추가하고, p리스트에도 추가한 뒤에 vis[r]=1한다.

 

이렇게 되면 마지막에는 p값에 파티를 통해 진실을 알게된 모든 사람이 담기게 된다.

이를 다시 한번 party리스트와 비교하여 되는 리스트만 뽑아주면 되겠다.

n,m=map(int,input().split())
p=list(map(int,input().split()))
party=[]
for x in range(m):
    v=list(map(int,input().split()))
    party.append(v[1:])
if p[0]==0:
    print(m)
else:
    del p[0]
    stack=[]
    stack.extend(p)
    vis=[0 for _ in range(n+1)]
    for x in p:
        vis[x]=1
    while stack:
        x=stack.pop()
        for t in party:
            if x in t:
                for r in t:
                    if vis[r]==0:
                        stack.append(r)
                        p.append(r)
                        vis[r]=1
    cnt=0
    for x in party:
        ck = 0
        for y in p:
            if y in x:
                ck=1
        if ck==0:
            cnt+=1
    print(cnt)