백준 : 17485 진우의 달여행 - 파이썬(python)

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

17485번: 진우의 달 여행 (Large)

주어진 길만보고 bfs로 푸는건 줄 알았는데 아니었다 그냥 구현해서 하나하나 더해보는 방식으로 풀어보려다가 생각이 잘안나서 블로그 글을 참조 했습니다.

출처

https://maeng2world.tistory.com/470

1. N, M, map 입력 받습니다.
2. dp용으로 사용할 3차원 배열을 만듭니다.
   • 방향 정보가 들어가 있으므로 3차원으로 만듭니다.
   • 초기 값은 최대 값으로 채워줍니다.
     • dp[y][x][0]: dp[y-1][x+1]의 최솟 값 + map[y][x]
     • dp[y][x][1]: dp[y-1][x]의 최솟 값 + map[y][x]
     • dp[y][x][2]: dp[y-1][x-1]의 최솟 값 + map[y][x]
3. dp에서 y == 0인 경우, map 값을 초기 값으로 채워줍니다.
4. 각각의 경우에 따라 dp를 진행합니다. (0 < y < N)
   • x == 0 인 경우: ↘로 오는 방향이 존재하지 않음
   • x == M-1인 경우: ↙로 오는 방향이 존재하지 않음
5. dp를 모두 채우고 나서, N-1번째 행에 존재하는 값 중 최솟값을 구합니다.

• 시간복잡도 : O(3NM) => O(NM)

2. 코드

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
MAX_VAL = 100 * 1000 + 1
dp = [[[MAX_VAL]*3 for _ in range(M)] for _ in range(N)]
for y in range(N):
    if y == 0:
        for x in range(M):
            for d in range(3):
                dp[y][x][d] = board[y][x]
    else:
        for x in range(M):
            if x == 0:
                dp[y][x][0] = min(dp[y-1][x+1][1], dp[y-1][x+1][2]) + board[y][x]
                dp[y][x][1] = dp[y-1][x][0] + board[y][x]
            elif x == M-1:
                dp[y][x][1] = dp[y-1][x][2] + board[y][x]
                dp[y][x][2] = min(dp[y-1][x-1][0], dp[y-1][x-1][1]) + board[y][x]
            else:
                dp[y][x][0] = min(dp[y-1][x+1][1], dp[y-1][x+1][2]) + board[y][x]
                dp[y][x][1] = min(dp[y-1][x][0], dp[y-1][x][2]) + board[y][x]
                dp[y][x][2] = min(dp[y-1][x-1][0], dp[y-1][x-1][1]) + board[y][x]
answer = 1e9
for x in range(M):
    answer = min(min(dp[N-1][x]), answer)
print(answer)