[2020ココ実習]慶州建設

from collections import deque
def solution(matrix):

    N, M = len(matrix), len(matrix)
    dx = [0, -1, 0, 1]  # 상 좌 하 우
    dy = [-1, 0, 1, 0]

    def iswall(nx, ny):
        if nx < 0 or ny < 0:
            return False
        if nx >= N or ny >= M:
            return False
        if matrix[nx][ny] == 1:
            return False
        return True

    def bfs(start):
        queue = deque([start])
        matrix[0][0]= 1
        min_money = [[100000000] * N for _ in range(M)]
        min_money[0][0] = 0

        while queue:
            x,y,cost,head = queue.popleft() # 좌표
            for i in range(4): # 상 하 좌 우 좌표 살피기
                nx, ny=x+dx[i], y+dy[i]
                if iswall(nx,ny) :
                    if head != i: # 곡선 도로(모서리 + 직선)
                        n_cost = cost+ 600
                    else : # 직선 도로(직선)
                        n_cost = cost + 100
                    if n_cost < min_money[nx][ny]: # 최솟값인 경우
                        min_money[nx][ny] = n_cost
                        queue.append([nx, ny, n_cost, i])
        return min_money[-1][-1]
    return min(bfs((0,0,0,2)),bfs((0,0,0,3))) # 시작은 우, 하

matrix = [[0,0,0],[0,0,0],[0,0,0]]
print(solution(matrix))