[PS] 1043. 거짓말

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

1043번: 거짓말

---

문제 요약

지민이는 모든 파티에 참가하는데 A라는 이야기를 모든 파티에서 발설할 예정이다. 그러나 진실과는 다르게 더 과장해서 말하고 싶어한다. 이미 진실을 아는 사람이거나 진실을 들은 사람에게는 과장되게 말할 수 없다. 반대로, 과장된 이야기를 들은 사람은 진실을 들을 수 없다. 아래와 같은 입력이 들어왔을 때 과장된 이야기를 할 수 있는 파티의 최대 개수를 구하시오.

8(사람의 수) 5(파티의 수)
3(진실을 아는 사람의 수) 1 2 7(사람의 번호)
2(파티에 오는 사람의 수) 3 4(사람의 번호)
1(파티에 오는 사람의 수) 5(사람의 번호)
2(파티에 오는 사람의 수) 5 6(사람의 번호)
2(파티에 오는 사람의 수) 6 8(사람의 번호)
1(파티에 오는 사람의 수) 8(사람의 번호)

---

문제 접근

첫번 째,

문제를 읽자마자 그래프를 이용한 BFS로 풀어야겠다는 생각이 들어, 막무가내로 그래프를 구현하였다.

 

각 파티를 배열로 선언한다.

[1번(듣지않음), 2번(듣지않음), ... , 5번(듣지않음)]

위의 배열이 하나의 노드가 되도록 구성하였다.

 

반복문을 이용하여 위 노드로부터 자식 노드를 생성한다.

[1번(진실), 2번(듣지않음), ... , 5번(듣지않음)], - 1️⃣

[1번(듣지않음), 2번(진실), ... , 5번(듣지않음)],

...

[1번(듣지않음), 2번(듣지않음), ... , 5번(진실)],

 

[1번(과장), 2번(듣지않음), ... , 5번(듣지않음)],

[1번(듣지않음), 2번(과장), ... , 5번(듣지않음)],

...

[1번(듣지않음), 2번(듣지않음), ... , 5번(과장)]

 

이렇게 생성된 자식노드로부터 다시 같은 방식으로 자식노드를 생성한다.

아래는 1️⃣노드로부터 생성된 자식노드이다.

[1번(진실), 2번(진실), ... , 5번(듣지않음)],

...

[1번(진실), 2번(듣지않음), ... , 5번(진실)],

 

[1번(진실), 2번(과장), ... , 5번(듣지않음)],

...

[1번(진실), 2번(듣지않음), ... , 5번(과장)]

 

이와 같은 방식으로 이야기를 듣지 않은 파티가 없을 때 까지 반복 진행한다. 도중에 모순(진실을 들은 사람이 과장을 듣거나 과장을 들은사람이 진실을 들은 경우)이 발생한 노드는 바로 삭제하고 자식 노드를 생성하지 않는다.

 

최종적으로 생성된 노드를 순차 탐색하며, 과장을 들은 파티 개수의 최댓값을 구한다.

 

Python Code

import sys
from collections import deque
import copy

N, M = map(int, sys.stdin.readline().split())
parties = [set() for i in range(M)]

know_line = list(map(int, sys.stdin.readline().split()))
knows = set()
for i in range(len(know_line)-1):
  knows.add(know_line[i+1])

for i in range(M):
  party_line = list(map(int, sys.stdin.readline().split()))
  for j in range(len(party_line)-1):
    parties[i].add(party_line[j+1])

# print(knows, parties)

def make():
  return {
    'knows': knows.copy(),
    'overs': set(),
    'said': [False for i in range(M)],
    'overAction': 0
  }

def over_acting(element, party_idx):
  element['said'][party_idx] = True
  element['overs'] |= parties[party_idx]
  element['overAction'] += 1

def true_acting(element, party_idx):
  element['said'][party_idx] = True
  element['knows'] |= parties[party_idx]

def is_true(element):
  if len(element['knows'].intersection(element['overs'])):
    return False
  return True

result = 0

bfs = deque()
bfs.append(make())
for c in range(M):
  for d in range(len(bfs)):
    poped = bfs.popleft()
    for i in range(M):
      if not poped['said'][i]:
        new_el1 = copy.deepcopy(poped)
        true_acting(new_el1, i)
        bfs.append(new_el1)
        new_el2 = copy.deepcopy(poped)
        over_acting(new_el2, i)
        bfs.append(new_el2)

while bfs:
  poped = bfs.popleft()
  if is_true(poped) and poped['overAction'] > result:
    result = poped['overAction']

print(result)

결과는 망했다. 정답은 도출하나, 파티가 6~7개 이상인 경우 부터 시간이 매우 오래걸리기 시작했다.

 

다른 방식이 필요하였다.

 

두번 째,

사람간의 연결(서로 같은 파티에 참가)을 나타내는 그래프를 구현하도록 하였다.

 

graph = [set(1번 사람과 연결된 사람), set(2번 사람과 연결된 사람), ... , set(n번 사람과 연결된 사람)]

 

위의 그래프를 BFS 탐색을 하여, 진실을 들을 수 밖에 없는 사람과 아닌 사람의 집단을 구별하였다.

 

그 후 다시 파티를 순차탐색하여, 진실을 들을 수 밖에 없는 사람이 한 명도 존재하지 않는 파티의 개수(= 과장된 이야기를 듣는 최대의 파티 개수)를 계산하였다.

 

Python Code

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

know_line = list(map(int, sys.stdin.readline().split()))
connections = [set() for i in range(N+1)]
knows = [False for i in range(N+1)]
dq = deque()
for i in know_line[1:]:
  dq.append(i)

parties = [set() for i in range(M)]
for i in range(M):
  party_line = list(map(int, sys.stdin.readline().split()))
  for j in range(len(party_line)-1):
    parties[i].add(party_line[j+1])


for party in parties:
  for person in party:
    connections[person] |= party - {person}

while dq:
  person = dq.popleft()
  if not knows[person]:
    knows[person] = True
    for neighbor in connections[person]:
      dq.append(neighbor)

# print(knows)

know_set = set()
for i in range(len(knows)):
  if knows[i]:
    know_set.add(i)

result = 0

for party in parties:
  if len(party.intersection(know_set)) < 1:
    result += 1

print(result)

정답이었다.