[BaekJoon] 백준 1043번 : 거짓말

1043번 : 거짓말

단순할 줄 알았는데 꽤 복잡해서 시간이 걸렸던 문제이다.

파티에 오는 인원들을 그래프로 만들어 탐색을 하면 된다.

처음엔 진실을 아는 사람과 연결되지 않은 그래프 개수를 구하면 될 줄 알았지만 아니었다.

그래프 개수가 아니라 파티의 개수를 구해야 한다.

그런데 파티에 참여하는 사람들이 중복 된다면 그래프도 엮여 있어 BFS 를 수행하는 경우 난감해 질 수 있다.

해결책은 파티마다 먼저 오는 사람을 부모 노드로 취급 해 그래프를 만들고

BFS 를 시작 할 때 시작 하는 노드가 부모 노드라면 값을 올려주면 된다.

그 상태로 BFS 를 수행 하다가 진실을 아는 사람의 노드를 방문하게 되면 0을 반환한다.

BFS 방문 순서도 노드 순서가 아닌 파티 별 부모 노드 순서로 방문을 한다.

만약 이렇게 파티 그래프가 주어진다면 1에서 두 번 BFS 를 시작해야하기 때문이다.

이 경우 1에서 두 번 시작 해 모두 진실을 알고 있는 3을 방문하지 않기 때문에 답은 2가 된다.

---

import sys
from collections import deque


def BFS(parent_arr, graph, know_truth, start):
	visit = []
	queue = deque([start])
	result = 0

	if start in parent_arr:
		result = 1

	while queue:
		cur_node = queue.popleft()
		if cur_node in know_truth:
			return 0

		visit.append(cur_node)

		for val in graph[cur_node]:
			if val not in visit:
				queue.append(val)
				visit.append(val)
	return result


def find_max_lie(party_arr, parent_arr, graph, know_truth):
	answer = 0

	for party in party_arr:
		answer += BFS(parent_arr, graph, know_truth, party[0])
	return answer


people_cnt, party_cnt = map(int, input().split())
know_cnt = list(map(int, input().split()))
party_arr = []
for _ in range(party_cnt):
	party = list(map(int, sys.stdin.readline().rsplit()))[1:]
	if len(party) == 0:
		continue
	else:
		party_arr.append(party)
if know_cnt[0] != 0:
	know_truth = [val for val in know_cnt[1:]]
else:
	know_truth = []

graph = {i + 1: [] for i in range(people_cnt)}
parent_arr = []

for party in party_arr:
	parent = party[0]
	parent_arr.append(party[0])
	for child in party[1:]:
		graph[parent].append(child)
		graph[child].append(parent)

print(find_max_lie(party_arr, parent_arr, graph, know_truth))