[파이썬] 백준 17485 : 진우의 달 여행 (Large) (골드5)

[파이썬] 백준 17485 : 진우의 달 여행 (Large) (골드5)

• https://www.acmicpc.net/problem/17485

---

풀이

방향성 생각

• x,y 이외에 같은 노드에서도 방향을 기억해야하는 문제
• 3차원 바텀업 DP로 풀이

 

---

전체코드

import sys
input = sys.stdin.readline

H,W = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(H)]

dp = [[[10**5+1]*W for _ in range(H)] for _ in range(3)]
for d in range(3):
    dp[d][0] = arr[0][:]

dires = [-1,0,1]
for y in range(1,H):
    for x in range(W):
        for d in range(3):
            px = x - dires[d] 
            if 0 <= px < W:
                for pd in range(3):
                    if pd != d:
                        dp[d][y][x] = min(dp[d][y][x], dp[pd][y-1][px] + arr[y][x])

print(min(min(dp[d][-1]) for d in range(3)))

코멘트

• 한 노드를 업데이트 할 때, 여러 방향에서 업데이트 되는 경우 배열의 양 끝에서 인덱스 에러가 발생한다.
• 현재 노드 x를 기준으로 방향을 하나 정해주고 방향 별로 배열 업데이트 하기.