Enochkon's blog

문제

코드

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를 넣어줘서 없는 경로라는 것을 표시한다

문제

코드

from collections import deque

n,m=map(int,input().split())
arr = []
check= [[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(m):
    q.append((0,i,arr[0][i],'0'))
    while len(q)>0:
        ci,cj,count,direction=q.popleft()
        if check[ci][cj]==0 or check[ci][cj]>count:
            check[ci][cj]=count
        for a,b,c in d:
            if(c==direction):
                continue
            ni=ci+a
            nj=cj+b
            if(0<=ni<n and 0<=nj<m):
                q.append((ni,nj,count+arr[ni][nj],c))
print(min(check[n-1]))

풀이

• 위부터 아래로 내려갈때에 연료를 최소로 사용하는 경로를 찾아라

1. 각 경로의 연로를 입력 받고, 새로운 check 배열을 생성한다.
2. 출발지점들을 q에 넣고, bfs를 돌리며 아래로 나아간다.
   1. 같은방향으로 두번 가지 않게 ‘l’, ‘b’, ‘r’로 구분해서 체크한다.
   2. 만약 현재 위치의 check배열이 0이거나 현재 count보다 크면 count를 넣어준다
3. bfs를 전부 돌린 후 경로의 제일 끝 부분중 최소값을 출력한다.