이번 문제는 다이나믹 프로그래밍을 활용하여 해결하였다. 이동하면서 얻을 수 있는 모든 경우의 수를 저장해야 하고 그때 그때 가장 최선의 값을 저장해야 한다. 이 과정을 도식화하면 다음과 같다.

• 미로를 maze에 저장하였고 dp를 통해 메모라이제이션을 하였다.
• dp[0][i], dp[i][0]을 우선 dp[0][i-1]+maze[0][i], dp[i-1][0]+maze[i][0]으로 갱신해준다.
• dp[1][1]을 예로 들면 dp[0][0], dp[0][1], dp[1][0] 중 가장 큰 값에 maze[1][1]을 더한 값으로 갱신한다. 위의 그림에서는 1, 1, 3 중 3이 가장 크므로 3+0의 값이 dp[1][1]의 값이 된 것이다.
• 이 과정을 반복하여 dp[n-1][m-1]을 구한다. dp[n-1][m-1]은 여기서 dp[2][3]이므로 dp[1][2]=6, dp[2][2]=25, dp[1][3]=15 중에서 가장 큰 dp[2][2]에 maze[2][3]을 더한 값 31을 취하게 된다.

그러므로 이 문제의 점화식은 다음과 같이 나타낼 수 있다.
dp[i][j]=max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+maze[i][j]

• n, m을 입력받는다.
• 미로를 나타내는 리스트 maze를 선언한다.
• n번 반복하는 for문을 돌린다.
  -> maze를 입력한다.
• dp 리스트를 n*m에 0을 채워 선언한다.
• dp[0][0]을 maze[0][0]으로 갱신한다.
• 1부터 m-1까지 반복하는 i에 대한 for문을 돌린다.
  -> dp[0][i]를 dp[0][i-1]+maze[0][i]로 갱신한다.
• 1부터 n-1까지 반복하는 i에 대한 for문을 돌린다.
  -> dp[i][0]을 dp[i-1][0]+maze[i][0]으로 갱신한다.
• 1부터 n-1까지 반복하는 i에 대한 for문을 돌린다.
  -> 1부터 m-1까지 반복하는 j에 대한 for문을 돌린다.
  --> dp[i][j]를 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 가장 큰 값에 maze[i][j]를 더한 값으로 갱신한다.
• dp[n-1][m-1]을 출력한다.

Code

n, m=map(int, input().split())
maze=[]
for _ in range(n):
    maze.append(list(map(int, input().split())))
dp=[[0]*m for _ in range(n)]
dp[0][0]=maze[0][0]
for i in range(1,m):
    dp[0][i]=dp[0][i-1]+maze[0][i]
for i in range(1, n):
    dp[i][0]=dp[i-1][0]+maze[i][0]
for i in range(1, n):
    for j in range(1, m):
        dp[i][j]=max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+maze[i][j]
print(dp[n-1][m-1])