경주로 건설 - 프로그래머스

경주로 건설 - 프로그래머스

from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def solution(board):
    q = deque([])
    q.append((0, 0, 0, 0))
    ret = list([0] * len(board) for _ in range(len(board)))
    
    while q:
        x, y, d, cnt = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < len(board) and 0 <= ny < len(board):
                if board[ny][nx] != 1:
                    if nx == 0 and ny == 0:
                        continue

                    if x == 0 and y == 0:
                        temp = cnt + 100
                    else:
                        if d == i:
                            temp = cnt + 100
                        else:
                            temp = cnt + 600

                    if ret[ny][nx] == 0:
                        ret[ny][nx] = temp
                        q.append((nx, ny, i, temp))
                    else:
                        if ret[ny][nx] >= temp:
                            ret[ny][nx] = temp
                            q.append((nx, ny, i, temp))
    return ret[-1][-1]