[백준] 17485 진우의 달 여행 (Large) python

문제

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

코드

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

n,m=map(int,input().split())
arr = []
check= [[[0,0,0] for _ in range(m)] for _ in range(n)]
d=[(1,0,'b'),(1,-1,'l'),(1,1,'r')]
q=deque()

for i in range(n):
    arr.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        count=0
        if(i==0):
            check[i][j][0]=check[i][j][1]=check[i][j][2]=arr[i][j]
            continue
        if(i==1):
            if j==0:
                check[i][j][0]=float("inf")
                check[i][j][1]=arr[i][j]+arr[i-1][j]
                check[i][j][2]=arr[i][j]+arr[i-1][j+1]
            elif j==m-1:
                check[i][j][2]=float("inf")
                check[i][j][0]=arr[i][j] + arr[i-1][j-1]
                check[i][j][1]=arr[i][j] + arr[i-1][j]
            else:
                check[i][j][2]=arr[i][j] + arr[i-1][j+1]
                check[i][j][0]=arr[i][j] + arr[i-1][j-1]
                check[i][j][1]=arr[i][j] + arr[i-1][j]
            continue
        if j==0:
            check[i][j][0]=float("inf")
            check[i][j][1]=arr[i][j] + check[i-1][j][2]
            check[i][j][2]=arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])
        elif j==m-1:
            check[i][j][0]=arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
            check[i][j][1]=arr[i][j] + check[i-1][j][0]
            check[i][j][2]=float("inf")
        else:
            check[i][j][0]=arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
            check[i][j][1]=arr[i][j] + min(check[i-1][j][0],check[i-1][j][2])
            check[i][j][2]=arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])

res=float("inf")
for i in range(m):
    res=min(min(check[n-1][i]),res)
print(res)

풀이

• 최소 비용의 경로 찾기

1. 각각의 경로에 드는 연료의 양을 입력받고, 누적 연료를 입력할 check 배열을 추가해준다.
   1. check[i][j][l] : i는 열, j는 행 그리고 l은 바로 전 경로가 어디서 왔는지를 나타낸다
   • l에서 0은 왼쪽 위에서 내려온것, 1은 바로 위에서 내려온것, 2는 오른쪽 위에서 내려온것 이다.
2. 첫번째 구역부터 반복문으로 탐색해준다.
   1. 제일 첫번째인 i==0인 곳은 그 구역 연료의 양을 추가해준다
   2. 두번째인 i==1은 바로 위와 현재 경로만 생각해주면 되므로 각각의 값을 추가해준다.
   3. 그 뒤부터는 최소 연료양의 경로를 추가해준다. 단, 같은 방향이 연속되면 안되기 때문에 방향을 생각해서 계산한다.

 

 

우선 각각의 방향에서 온 값을 계산한다
1. 왼쪽에서 내려온 경우 (l==0) check[i][j][0]일때는 왼쪽으로 두번 연속으로 내려오면 안되므로 오른쪽, 왼쪽 으로 내려왔거나 아래 왼쪽으로 내려온 경우만 생각해주면 된다.
즉 arr[i][j] + min(check[i-1][j-1][1],check[i-1][j-1][2])
현재의 값 + (check[i-1][j-1][1] 아래로 내려온 후 왼쪽에서 온 경우와, check[i-1][j-1][2] 오른쪽에서 내려온 후 왼쪽에서 내려온 경우 중 작은 값은 넣어준다.)

2. 바로 아래로 내려온 경우 (l==1)
arr[i][j] + arr[i][j] + min(check[i-1][j][0],check[i-1][j][2])
현재의 값 + (check[i-1][j][0] 왼쪽에서 내려온 후 아래로 내려온 경우와, check[i-1][j][2] 오른쪽에서 내려온 후 아래로 내려온 경우 중 작은 값은 넣어준다.)

3. 오른쪽에서 아래로 내려온 경우 (l==2)
arr[i][j] + min(check[i-1][j+1][0],check[i-1][j+1][1])
현재의 값 + (check[i-1][j+1][0] 왼쪽에서 내려온 후 오른쪽으로 내려온 경우와, check[i-1][j+1][1] 바로 아래로 내려온 후 오른쪽에서 내려온 경우 중 작은 값은 넣어준다.)

→ 이 조건을 만족한 후 제일 마지막 행에서 제일 작은 값을 찾아서 출력한다.

특이사항

• 유사문제 17484에서는 bfs로 풀었지만 이번에는 그럴경우 시간초과가 난다. DP로 풀어야 하는문제
• 기본적으로 세 방향에서 내려온 값들을 찾지만, 범위를 벗어나거나 하는 경우에는 inf를 넣어줘서 없는 경로라는 것을 표시한다