[Python] 백준 1043번: 거짓말

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

1043번: 거짓말

 

import sys
input = sys.stdin.readline


def visitPartyKnowledgeablePeoplepartyToAttend():
    for ppl in range(1, N+1):
        if isPeopleKnowledgeable[ppl] == True:
            for pty in partyToAttend[ppl]:
                if isPartyKnowledgeable[pty] == False:
                    setIsPartyKnowledgeableTrue(pty)


def setIsPartyKnowledgeableTrue(party):
    isPartyKnowledgeable[party] = True
    for ppl in partyPeople[party]:
        isPeopleKnowledgeable[ppl] = True

        for pty in partyToAttend[ppl]:
            if isPartyKnowledgeable[pty] == False:
                setIsPartyKnowledgeableTrue(pty)


def getUnknowledgeablePartyCount():
    unknowledgeablePartyCount = 0

    for i in range(M):
        if isPartyKnowledgeable[i] == False:
            unknowledgeablePartyCount += 1

    return unknowledgeablePartyCount


if __name__ == '__main__':
    N, M = map(int, input().split())

    isPeopleKnowledgeable = [False]*(N + 1)
    curNums = list(map(int, input().split()))
    for i in range(1, curNums[0] + 1):
        isPeopleKnowledgeable[curNums[i]] = True

    partyPeople = []
    partyToAttend = [[] for _ in range(N + 1)]

    for i in range(M):
        curNums = list(map(int, input().split()))

        partyPeople.append(curNums[1:])
        for j in range(1, curNums[0] + 1):
            partyToAttend[curNums[j]].append(i)

    isPartyKnowledgeable = [False]*M

    visitPartyKnowledgeablePeoplepartyToAttend()

    unknowledgeablePartyCount = getUnknowledgeablePartyCount()
    print(unknowledgeablePartyCount)

 

진실을 알고 있는 사람이 1명이라도 있으면, 그 파티에 참가한 모든 사람들도 진실을 알게 된다. 따라서, 다른 참가자들이 참여하는 다른 파티들에도 진실이 '전염'된다.

예제 입력 5의 경우를 들어보자.

10 9

4 1 2 3 4

2 1 5

2 2 6

1 7

1 8

2 7 8

1 9

1 10

2 3 10

1 4

파티 7(2 3 10)을 보자. 사람 3이 진실을 알고 있으므로, 해당 파티에 참여한 10도 진실을 알게된다. 이에 따라, 사람 10이 참여한 다른 파티인 파티 6(1 10)에도 진실을 말해야한다.

 

DFS로 풀었고, 4개의 중요한 리스트가 쓰인다.

 - isPeopleKnowledgeable: 이 사람이 진실을 알고 있는가?

 - isPartyKnowledgeable: 이 파티에서 진실을 말해야하는가?

 - partyPeople: 파티에 참여하는 사람들의 리스트

 - partyToAttend: 사람들이 참가하는 파티의 리스트

 

우선 visitPartyKnowledgeablePeopleToAttend() 함수를 통해, 처음부터 진실을 알고 있는 사람들이 참여한 파티들을 '탐색'한다. 여기서 '탐색'한다는 것은 setIsPartyKnowledgeableTrue()라는 DFS 함수로 파티에 대해 탐색을 시작한다는 것이다. 해당 함수는 인자에 파티를 받는다. 이중 for문을 쓰는데, 해당 파티에 참석하는 사람들(partyPeople)을 돌고, 또 그 사람들이 참석하는 파티들(toAttend)에 대해 탐색을 진행한다.

 

이렇게 isPartyKnowledgeable이 적당한 값을 취하게 되면, 마지막으로 모든 파티를 돌며 isPartyKnowledgeable이 False일 때마다 카운트를 증가시켜서 과장된 이야기를 이야기할 파티의 개수를 얻고 출력시킨다.