백준|1043번|거짓말

문제설명
지민이는 파티에 가서 이야기를 말할 때, 있는 그대로 진실을 말하거나 엄청나게 과장해서 말한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 몇몇 사람들은 그 이야기의 진실을 알고 있다. 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 어떤 사람이 어떤 파티에서는 진실을 듣고, 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 문제입니다.

작동 순서
1. 사람의 수와 파티의 수를 입력받습니다.
2. 진실을 아는 사람들을 목록을 입력받고 진실을 아는 사람 큐에 삽입합니다.
3. 진실을 아는 사람들이 참가하는 파티의 목록을 찾고 그 파티에 참가하는 사람들도 진실을 아는 사람 큐에 삽입합니다.
4. 진실을 아는 사람이 어떤 파티에 참가할 경우 그 파티는 거짓말을 할 수 없는 파티로 지정하고 그 파티에 참가하는 사람들을 진실을 아는 사람 큐에 삽입합니다.
5. 진실을 아는 사람 큐에 더 이상 남은 사람이 없을 때까지 연산을 수행합니다.
6. 파티들중 진실을 말하지 않아도 되는 파티들의 개수를 출력합니다.

소스코드

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())

knowPeoples = deque(map(int, sys.stdin.readline().split()))
knowPeoples.popleft()

party = []
visited = [False for _ in range(N+1)]
trueParty = [False for _ in range(M)]
count = M

for i in range(M):
    party.append(list(map(int, sys.stdin.readline().split()))[1:])

while len(knowPeoples) > 0:
    knowPeople = knowPeoples.popleft()
    visited[knowPeople] = True
    for i in range(M):
        for j in range(len(party[i])):
            if party[i][j] == knowPeople:
                if not trueParty[i]:
                    trueParty[i] = True
                    count -= 1
                for k in range(len(party[i])):
                    if not visited[party[i][k]]:
                        knowPeoples.append(party[i][k])

print(count, end="")

후기
제가 푼 방식은 단순한 그래프 탐색 방식인데 다른 분들의 풀이를 보니 유니온파인드라는걸 사용하셨던 것 같습니다. 역시 알고리즘 공부는 끝이 없는 것 같습니다.