[백준 1043번] 거짓말

 

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

import sys
from itertools import permutations
from collections import deque

input = sys.stdin.readline

# 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다
# 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다

# 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다
# 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것

# 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다

# 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다

# 사람의 수 N, 그리고 그 이야기의 진실을 아는 사람이 주어진다
# 그리고 각 파티에 오는 사람들의 번호가 주어진다

# 지민이는 모든 파티에 참가해야 한다

# 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램

n, m = map(int,input().split())

know_list = set(list(map(int,input().split()))[1:]) # 1 2 3 4

party = [set() for _ in range(m)]

graph = [set() for _ in range(n+1)]

answer = 0

for i in range(m):
    numbers = list(map(int,input().split()))[1:]
    party[i] = set(numbers)

    if len(numbers) >= 2 :
        path = list(permutations(numbers,2))

        for a,b in path:
            graph[a].add(b)

graph = [list(x) for x in graph]

def bfs(index):

    global know_list

    q = deque([index])

    visited = [False]*(n+1)

    visited[index] = True

    temp = {index}

    while q:
        v = q.popleft()

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                temp.add(i)

    if index in know_list:
        know_list |= temp

for i in range(len(party)):
    for j in party[i]:
        bfs(j)


for i in range(m):
    if not know_list & party[i]:
        answer += 1

print(answer)


# for i in range(m):
#     temp = know_list & party[i]
#     temp2 = party[i] | know_list

#     if temp:
#         know_list = temp2

이번 문제는 N명의 사람들 중 진실을 아는 사람의 번호와 각 파티에 참여하는 사람들의 번호가 주어졌을 때 거짓말이 소문나지 않으면서 과장할 수 있는 파티 개수의 최댓값을 구하는 문제이다.

결론적으로 진실을 이미 알고 있거나, 파티로 인해 진실을 알게 될 수 밖에 없는 사람들이 한명도 없는 파티의 개수를 구해야한다.

처음에는 단순하게 모든 파티를 순회하면서 이미 진실을 아는 사람(know_list)들이 파티에 존재하면 다른 사람들도 해당 집합에 넣어주는 방식으로 구현했는데, 이렇게 되면 모든 경우의 수를 구하지 못하고 예외가 발생하게 된다.(주석처리된 코드)

따라서 진실에 대한 소문이 퍼지는 모든 경로를 탐색하기 위해 N명의 연결 정보를 저장할 수 있는 graph 라는 2차원 배열을 선언해주었고, 순열(permutations)를 활용하여 진실을 아는 사람들 간에 연결 관계를 모두 저장해주었다.

그 후 BFS 알고리즘을 사용하여 진실을 아는 모든 사람들로부터 완전탐색을 하여 파티로 인해 진실을 알게 되는 사람들까지 전부 know_list 집합에 저장하였다.

그 후 모든 파티의 구성원과 진실을 아는 사람들의 집합(know_list)에 교집합이 하나라도 없을 경우에 answer를 카운팅 해주었다.

그래프와 BFS 알고리즘을 활용하여 풀이할 수 있었던 좋은 문제였다 :)