import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
graph = []
for i in range(N):
graph.append(list(map(int,input().split())))
count = 0
def DFS(y,x,state):
global count
if y==x==N-1: #도착시 개수 세기
count += 1
return
if state == 0: #가로일때
if x+1<N:
if graph[y][x+1]==0:
DFS(y,x+1,0)
if x+1<N and y+1<N:
if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
DFS(y+1,x+1,1)
elif state == 1: #대각선일때
if x+1<N:
if graph[y][x+1]==0:
DFS(y,x+1,0)
if x+1<N and y+1<N:
if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
DFS(y+1,x+1,1)
if y+1<N:
if graph[y+1][x]==0:
DFS(y+1,x,2)
else: #세로일때
if x+1<N and y+1<N:
if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
DFS(y+1,x+1,1)
if y+1<N:
if graph[y+1][x]==0:
DFS(y+1,x,2)
DFS(0,1,0)
print(count)
고전적인 DFS 방식으로 해결했다. 다만 python3로는 시간초과가 발생하여 pypy3로 제출해서 통과하였다.
다른 사람들 풀이를 참고하니 python3로 통과하기 위해서는 DP 방식을 이용해야 하는것 같다.
오늘의 교훈) 데이터가 크면 DP 방식을 이용하자