[Python] 카카오 2020 인턴쉽 - 경주로 건설 (BFS)

from collections import deque

def solution(board):
    ans = float('inf')
    n = len(board)
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    # (nx, ny, d) : cost
    visit = {(0,0,0):0, (0,0,1):0, (0,0,2) : 0, (0,0,3):0}
    que = deque()
    #초기값. x, y, dir = -1 , cost
    que.append((0,0,-1,0))

    #BFS
    while que:
        x, y, dir, cost = que.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            #이동 가능하면 (범위내이고 board[nx][ny]가 0이면)
            if -1 < nx < n and -1 < ny < n and not board[nx][ny]:
                ncost = cost
                #맨 처음
                if dir == -1:
                    ncost += 100
                #진행 방향 평행
                elif(dir - d) % 2 == 0:
                    ncost += 100
                #진행 방향 수직
                else: ncost += 600

                #도착 지점이라면 min값으로 갱신
                if nx == n-1 and ny == n - 1:
                    ans = min(ans, ncost)
                #방문하지 않았거나 || 방문 했을때보다 비용 적은 경우에 value(cost) 갱신, queue에 추가
                elif visit.get((nx, ny, d)) is None or visit.get((nx,ny, d)) > ncost:
                    visit[(nx, ny, d)] = ncost
                    que.append((nx, ny, d, ncost))
    return ans

if __name__ == "__main__":
    board = [[0,0,0],[0,0,0],[0,0,0]]
    solution(board)