11048: 이동하기

문제 링크

11048: 이동하기

구현 방식

• 2차원 미로여서 bfs로 풀려다가 시간초과, 메모리초과가 나서 삽질했다 (무작정 bfs로 푸는 건 안좋은 습관..)
• 이 문제는 dp로 풀면 쉽게 풀린다
  • [N+1][M+1]의 크기만큼 dp table을 생성해주고 2중 for문을 돌며 갱신해주면 된다
  • 점화식은 아래와 같다
    • dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + board[i-1][j-1]

코드

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
dx = (0, 1, 1)
dy = (1, 0, 1)

board = [list(map(int, input()[:-1].split())) for n in range(N)]
dp = [[0 for m in range(M+1)] for n in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + board[i-1][j-1]

print(dp[N][M])