백준 / 실버 1 / 1890 점프 / Python [DP, 부분합, BFS]

DFS: O(2^N) 시간초과

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0

def dfs(r, c):
    global ans
    if r == N-1 and c == N-1:
        ans += 1
        return
    if r <= N-1 and c <= N-1:
        j = board[r][c]
        dfs(r + j, c)
        dfs(r, c + j)
dfs(0, 0)
print(ans)

개선된 DFS: O(2^N) 시간초과

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0

def dfs(r, c):
    global ans
    if r == N-1 and c == N-1:
        ans += 1
        return
    j = board[r][c]
    if r + j <= N-1:
        dfs(r + j, c)
    if c + j <= N-1:
        dfs(r, c + j)
dfs(0, 0)
print(ans)

DP, 부분합, BFS: O(N^2)

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*N for _ in range(N)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        b = board[i][j]
        if b == 0:
            continue
        if i + b < N:
            dp[i+b][j] += dp[i][j]
        if j + b < N:
            dp[i][j+b] += dp[i][j]
print(dp[N-1][N-1])