풀이

처음에는 bfs로 푸려고 했으나 당연히 메모리 및 시간 초과... 배열의 크기가 클때는 완전탐색은 하지말자 ㅠㅠ...다이나믹 프로그래밍을 사용하는 경우를 정리를 잘 해놔야할 것 같다. 배열의 크기가 크고 누적값을 구하거나 기존 값의 영향을 받는거면 사용한다!

그래서 다이나믹 프로그래밍으로 풀어주었다. (r+1, c), (r, c+1), (r+1, c+1) 이런 방식으로만 이동할 수 있으니 반대로 (r-1, c), (r, c-1), (r-1, c-1)을 확인해주면서 가장 큰 값을 가져오게 했다.

import sys
from collections import deque


n, m = map(int, input().split())
lst =[[0]*(m+1)] + [[0]+list(map(int, input().split()))+[0] for i in range(n)] + [[0]*(m+1)]

dp = [[0]*(m+2) for _ in range(n+2)]
dp[1][1] = lst[1][1]


for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = lst[i][j] +max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

print(dp[n][m])