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 라는 알고리즘을 이용하는 것 같다.
물론 이번 문제에서는 사용하지 않아도 큰 상관이 없었지만 다른 문제에서는 또 어떨지 모르니 염두해 두어야겠다.
오늘의 교훈) 집합 자료형도 풀이에 고려하자