[백준 1043번] 거짓말 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N,M = map(int,input().split())  #사람수, 파티수

truelist = deque(list(map(int,input().split()))[1:])

party = []
for i in range(M):
  party.append(list(map(int,input().split()))[1:])

lielist =  deque()
countlist = []

def Party(partynum,count):
  truecount = liecount = 0
  for i in party[partynum]:
    if i in truelist:
      truecount += 1
    if i in lielist:
      liecount += 1
  if truecount == 0:
    if partynum == M-1:
      countlist.append(count+1)
      return
    lielist.extend(party[partynum])
    Party(partynum+1,count+1)
    for i in range(len(party[partynum])):
      lielist.pop()
  if liecount == 0:
    if partynum == M-1:
      countlist.append(count)
      return
    truelist.extend(party[partynum])
    Party(partynum+1,count)
    for i in range(len(party[partynum])):
      truelist.pop()

Party(0,0)
print(max(countlist))

 

전형적인 백트래킹 문제라고 생각하고 사실을 들은 그룹 deque와 거짓말을 들은 그룹 deque에 매번 파티인원을 extend 시켜주고, 그 이후에는 그만큼 pop 시켜주는 방식으로 해결하였다.

 

나의 방식도 꽤 빠른 시간내에 잘 돌아갔지만 다른 사람들의 풀이방식을 보니 set와 union(합집합)을 이용한 풀이가 많아보였다. union-find 라는 알고리즘을 이용하는 것 같다.

 

물론 이번 문제에서는 사용하지 않아도 큰 상관이 없었지만 다른 문제에서는 또 어떨지 모르니 염두해 두어야겠다.

 

 

 

오늘의 교훈) 집합 자료형도 풀이에 고려하자