[백준1043&파이썬] 적절한 자료구조 사용하기, 방문처리를 통해 무한루프에 빠지지 않게 하기

# 문제

백준 1043 거짓말 파이썬 풀이

1043번: 거짓말

# 코드

import sys
from collections import defaultdict
from collections import deque

def print2D(arr):
  for a in arr :
    print(a)

# 사람의 수 N, 파티의 수 M
N,M = map(int,sys.stdin.readline().split())

# 진실을 아는 사람의 수, 0번인덱스는 총 크기
trues = list(map(int,sys.stdin.readline().split()))
if trues[0] > 0 :
  trues = trues[1:]

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

visit_party = [True] * M # 파티 만큼
visit_person = [False] * (N+1) # 사람 수 만큼

# 그래프 탐색처럼 해보자!
dq = deque()

for true in trues :
  dq.append(true) # 사람을 넣는다. 사람을 기준으로 파티를 찾고 순회할 예정이다.

while len(dq) != 0 :
  poped = dq.popleft()
  visit_person[poped] = True # 방문처리 한다.

  for party_idx in d[poped] :
    if visit_party[party_idx] == False :
      continue
    else :
      visit_party[party_idx] = False

      for person in parties[party_idx] :
        if visit_person[person] == False :
          dq.append(person)

# print(visit_party)
# print(visit_person)

sum = 0
for result in visit_party :
  if result == True :
    sum += 1

print(sum)

 

# 풀이

• 참가자과 파티로 구분하여 생각했다.
• 각각 참가자가 속한 파티를 그룹화 했다.
• 진실을 아는 사람의 명단이 주어진다(trues) 그리고 그 trues명단에 있는 사람들이 참가하는 각각의 파티는 거짓말을 하면 안된다고 visit_party를 이용해 체킹한다.
• 이때, 해당 파티가 거짓말을 하면 안되는 파티라고 확정되는 순간, 해당 파티에 속한사람의 파티또한 거짓말을 하면 안된다. 이 과정이 재귀적으로 일어나게 된다.
• 그러나 순환참조로 인한 재귀에서 빠져나오지 못하는 문제가 생길 수 있기 때문에 visit_person이라는 것을 만들어 이미 체크한 사람이라면 deque에 넣지 않도록 했다. 
• 이번 문제는 적절한 자료구조들을 선택하고 연계하여 풀이하는게 핵심인거 같았다.