[BFS, DFS] 토끼야, 집가자

DFS

답은 맞는데, 시간 초과 뜸

import sys
input = sys.stdin.readline

n = int(input())
# g = [[0]*(n+1)] + [[0] + list(map(int, input().split())) for _ in range(n)]
g = [list(map(int, input().split())) for _ in range(n)]


dx = [0,1]
dy = [1,0]

visited = [[0]*len(range(n)) for _ in range(n)]
def DFS(x,y):
    global ways
    global visited
    if x==n-1 and y==n-1:
        ways+=1
        visited = [[0]*len(range(n)) for _ in range(n)]
        return

    if 0<=x<n and 0<=y<n and visited[x][y] == 0 and g[x][y] != 0:
        visited[x][y] = 1
        power = g[x][y]
        for c in range(2):
            nx = x + dx[c]*power
            ny = y + dy[c]*power
            DFS(nx,ny)

    return

ways = 0
DFS(0,0)
print(ways)

BFS

재도전!

# 돼락 
# 0515 하는 중

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]

dx = [0,1]
dy = [1,0]

visited = [[0]*len(range(n)) for _ in range(n)]
q = deque()
# deque은 append 랑 popleft 사용

# ---------- 하는 중
print(q)
def DFS(x,y):
    global ways
    global visited
    if x==n-1 and y==n-1:
        ways+=1
        visited = [[0]*len(range(n)) for _ in range(n)]
        return
        
    if 0<=x<n and 0<=y<n and visited[x][y] == 0 and g[x][y] != 0:
        visited[x][y] = 1
        power = g[x][y]
        for c in range(2):
            nx = x + dx[c]*power
            ny = y + dy[c]*power
            DFS(nx,ny)
        
    return

ways = 0
DFS(0,0)
print(ways)

BFS의 포인트  :  '큐' 자료구조의 사용

•  deque은 append 랑 popleft 사용

from collections import deque
q = deque()
q.append(0)

q.popleft()