[백준] 17484 진우의 달 여행 (Small) python

문제

17484번: 진우의 달 여행 (Small)

코드

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를 전부 돌린 후 경로의 제일 끝 부분중 최소값을 출력한다.