백준 boj. 17484 진우의 달 여행 [실버 🥈🥈🥈]

boj. XX 벽 부수고 이동하기2 [link] 랑 비슷한 유형의 실수를 했던 문제.

boj. 17484 진우의 달 여행 [실버 🥈🥈🥈]

f = open("input.txt", "r")
N, M = map(int, f.readline().split())

grid = []
for _ in range(N):
  grid.append(list(map(int, f.readline().split())))

dir = [(-1,-1), (-1,0), (-1,1)]
grid = grid + [[0]*M]

dp = [[[c]*3 for c in grid[0]]] + [[[int(1e8)]*3 for _ in range(M)] for _ in range(N)]

def find_min_cost(pi, pj, di):
  ## dp[pi][pj]에서 di 방향을 제외한 누적값 중 min값을 return
  mn_cost = int(1e8)

  for ci, c in enumerate(dp[pi][pj]):
    if ci != di:
      mn_cost = min(mn_cost, c)

  return mn_cost

for i in range(1, N+1): ## 1. 좌표순회
  for j in range(M):
    for di, (dx, dy) in enumerate(dir): # 2. 좌표 및 이전방향에 따라 dp table update
      pi, pj = i+dx, j+dy

      if 0<=pi<N+1 and 0<=pj<M: # 범위 내에 포함되는 경우만
        dp[i][j][di] = find_min_cost(pi, pj, di) + grid[i][j]

ans = 1e8
for each_moon in dp[-1]:       
  for each_dir in each_moon:
    ans = min(each_dir, ans)

print(ans)