[백준][Python] 16432 떡장수와 호랑이 : 백트래킹 설계.

checking을 어떻게 할것이냐? 그날 이떡을 먹었었다. 에 대한 체킹. 먹었었다면 굳이 다시 먹을 필요 없다.

 

import sys
input = sys.stdin.readline

def DFS(cnt,dduks,yesterday):
    global answer
    if cnt == N:
        for d in dduks:
            print(d)
        exit()
    for dduk in days[cnt]:
        if dduk != yesterday and not ate[cnt][dduk-1]:
            ate[cnt][dduk-1] = True
            DFS(cnt+1, dduks + [dduk],dduk)

N = int(input())
days = []
answer = []
for _ in range(N):
    m,*dduk = map(int, input().split())
    days.append(dduk)
ate = {i:[False for _ in range(10)] for i in range(N+1)}
DFS(0,[],0)
print(-1)