[백준] 거짓말

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

1043번: 거짓말

집합 자료구조를 활용하는 문제입니다. 

 

우선 문제부터 간단하게 요약해보면,

 

파티에서 지민이는 거짓말을 해야하는데, 이 때 이미 진실을 알고있는 사람들의 집합이 이미 주어집니다. 이 때, 지민이가 거짓말을 할 수 있는 파티의 최대 갯수를 구해야 합니다. 진실을 모르던 사람이라도 각각 다른 파티에서 진실과 거짓 두가지 모두를 듣게 되면, 진실을 알게 되므로 이런 상황 또한 고려해 주어야합니다. 

 

일단 다른 사람들의 더 편한 아이디어를 설명하고, 저의 풀이 또한 설명해 보도록 하겠습니다. 

 

<Solution>

문제를 다 풀고 다른 사람들의 풀이를 보았는데 훨씬 간단하게 하는 방법들이 있었습니다. 

일부 설명이 부족한 부분들이 있어서 추가 설명을 해보겠습니다. 

 

알고리즘 자체는 다음과 같습니다.

1. 파티의 갯수만큼 for loop를 돌린다 (이유 : 매번 거짓말을 할 수 있는 파티가 한개 씩 사라진다고 가정하면 최대 횟수는 파티의 갯수만큼이 될 것이다) 2. 매 for loop안에 다시 for loop를 만들어 순회한다. 3. 이때, 만약 진실을 알고있는 사람이 특정 파티에 존재하는 경우  4. 해당파티는 거짓말이 불가능한 파티로 마스킹한다.  5. 그리고 해당 파티에 참여한 인원을 진실을 알고 있는 사람의 list에 추가한다.

인터넷에 돌아다니는 풀이에는 1번에 대한 이유가 부실해서 추가해서 적었습니다. 

 

실제로 이렇게 구현한 코드는 다음과 같이 됩니다. (인터넷에서 가져온 풀이를 조금 바꾼것)

import sys

cnt_party = int(sys.stdin.readline().rstrip().split()[1])
witness_set = set(sys.stdin.readline().rstrip().split()[1:])

party_list = []
possible_list = []

for _ in range(cnt_party):
    party_list.append(set(sys.stdin.readline().rstrip().split()[1:]))
    possible_list.append(1)

for _ in range(cnt_party):
    for i, party in enumerate(party_list):
        if witness_set.intersection(party) and possible_list[i] != 0:
            possible_list[i] = 0
            witness_set = witness_set.union(party)

print(sum(possible_list))

# 출처 : https://itholic.github.io/kata-1043/

 

제가 푼 방법은 

input이 

3 4
1 3
1 1
1 2
2 1 2
3 1 2 3

다음과 같다고 가정하면, 

다음과 같은 과정을 거쳐서 문제를 해결합니다. 

사실 가장 중요한 아이디어는 각각의 party를 node로 하는 그래프를 구성하고, 각각의 connectivity를 어떠한 알고리즘으로라든 해결하면 되는 문제인 것 같습니다. 

 

실제 구현은 아래와 같습니다. people-party간의 그래프와 party-people간의 그래프를 두어 좀더 편리하게 계산을 할 수 있게 하였습니다. 

import sys
from collections import defaultdict
import itertools

# n: people m: party
n, m = list(map(int,sys.stdin.readline().rstrip().split()))
tmp = list(map(int,sys.stdin.readline().rstrip().split()))

num_truth = tmp[0]
list_truth = tmp[1:]

# build graph
party_people_graph = defaultdict(set)
people_party_graph = defaultdict(set)
for i in range(1,m+1):
    tmp = list(map(int,sys.stdin.readline().rstrip().split()))
    for element in tmp[1:]:
        people_party_graph[element].add(i)
        party_people_graph[i].add(element)

# print(party_people_graph)

connection_graph = defaultdict(set)
for i in list(itertools.combinations(list(range(1,m+1)), 2)):
    if party_people_graph[i[0]].intersection(party_people_graph[i[1]]):
        connection_graph[i[0]].add(i[1])
        connection_graph[i[1]].add(i[0])

# print(connection_graph)

visited = [False] * (m+1)

for ppl in list_truth:
    stack = list(people_party_graph[ppl])
    for s in stack:
        if not visited[s]:
            dfs_stack = [s]
            # dfs
            while(dfs_stack):
                s_ = dfs_stack.pop()
                visited[s_] = True # done search
                for e in connection_graph[s_]:
                    if not visited[e]:
                        dfs_stack.append(e)
                    else:
                        continue

print(visited.count(False)-1)