[백준/파이썬] 16432: 떡장수와 호랑이

와아아아~~ 엄청 오랜만에 문제를 풀었다 !!!!

문제 보러가기

풀이 😍

떡 종류는 1-9번!
N일 동안 떡 팔러 가는데, 그날 파는 떡의 종류들은 매일 달라진다.
전날의 떡과 오늘의 떡은 꼭 달라야 한다.

떡을 줄 방법이 있으면, 매일 호랑이한테 줄 떡을 순서대로 출력한다.
떡을 줄 방법이 없으면, -1을 출력한다.

처음에는 백 트래킹을 생각했다. 호랑이한테 줄 수 있는 떡의 경우들로 가지를 뻗어보다가, 처음으로 정답까지(N일 동안 호랑이한테 다른 떡 주는 경우) 가면 그만 탐색하면 되겠다고 생각했다 !! 또 N이 최대 1000이니까 그 정도면 dfs 를 돌릴 수 있다고 생각했다!

dfs 함수를 만들고 그 인자로 며칠인지(day), 그 동안 호랑이한테 준 떡들(history)을 넘겼다. 매일 호랑이한테 줄 수 있는 떡들로 다 가지를 뻗어보는 것이다! 그 동안 호랑이한테 준 떡을 아니까, 전날 호랑이한테 준 떡도 알 수 있다. 전날 준 떡과 줄 수 있는 떡이 다를 때만 가지를 뻗으면 된다.

이런 식으로 했더니, 처음에는 시간 초과가 나왔다.

게시판에 문제인 이유와 해결 방법이 나와있었다 !!

만약에 1-998일까지는 매일 떡을 1-9번 다 만들고, 999-1000일은 똑같은 떡을 만드는 경우를 생각해보면..
가지가 9(첫날 고르는 떡) X 8(다른 날들은 그 전날 고른 떡은 고를 수 없음)의 997제곱 X 1(999일에 고를 수 있는 떡이 1개) X 1(1000일에 고를 수 있는 떡이 1개) 만큼 뻗어지는 것이다. 엄청 엄청 경우가 많으니.. 시간 초과가 나는 것이다.

게시판에서 며칠인지, 그 전날 어떤 떡을 호랑이에게 주었는지로 방문 체크를 하면 된다는 걸 보았다. 그래서 2차원 리스트를 만들어서, 겉 리스트에는 몇번째 날인지/ 안의 리스트에는 전날 어떤 떡을 호랑이에게 주었는지를 두고 방문 체크를 했다.

N이 3인 경우!! 떡의 종류는 9개이니 내부 리스트의 length는 10으로 했다. (인덱스 편하게 사용하려고)

만약 이미 True로 체크되었으면, 특정일에 호랑이에게 특정 떡을 줬을 때 경우 & 그리고 그 이후 가지들은 이미 본 것이니까 안 봐도 된다! 

가능한 가지를 모두 그리지 않았는데도, 엄청 겹치는 부분이 많다는 걸 알 수 있다 !! 특정 일에 특정 떡을 줬으면, 그 이후 가지 치기는 동일하게 반복된다.

백트래킹 만으로 안되고 방문 체크까지 해야 해서 재미있었다 :) 

코드 🐼

import sys
sys.setrecursionlimit(10**4)
input=sys.stdin.readline

N=int(input())

rice_cakes_per_day = [] * N
for k in range(N):
    rice_cake = input().split()[1:]
    rice_cakes_per_day.append(rice_cake)

def dfs(day, history):
    global flag
    if flag:
        return

    if day == N:
        print('\n'.join(history.split()))
        flag = True
        return

    for cake in rice_cakes_per_day[day]: # 그 날의 떡 보면서
        # 첫날이라면
        if day == 0:
            visited[day+1][int(cake)] = True
            dfs(day+1, history+cake+' ') # 무조건 그 떡을 주고, 다음날로 넘어가기

        # 첫날 아닌데 전날과 안 겹치고 방문 안 했으면
        elif cake != history[-2] and not visited[day+1][int(cake)]:
            visited[day+1][int(cake)] = True
            dfs(day+1, history+cake+' ') # 그 떡을 주고, 다음날로 넘어가기


visited = [[False]*10 for _ in range(N+1)] # 날짜, 전날 준 떡
flag = False
dfs(0,'')

if flag == False: # 떡 줄 방법이 없으면 -1 출력
    print(-1)