프로그래머스 경주로 건설

bfs를 이용해 최단경로를 구하는데, 비용이 작은 방법이 있다면 수정하는 문제
https://programmers.co.kr/learn/courses/30/lessons/67259

같은 방향이라면 cost+100을 넣고,
다른 방향이라면 cost+600을 넣는다.

bfs로 탐색하던 중, 이미 온 경로인데, 그 경로보다 더 최소로 왔다면 최솟값을 바꾸는 방식이다. 방문자배열에 dp를 결합한 방식처럼 보인다.

import math
from collections import deque
def solution(board):
    def bfs(start):
        size = len(board)
        table = [[math.inf]*size for i in range(size)]
        table[0][0] = 0
        direction = [(-1,0),(1,0),(0,-1),(0,1)] ## 위:0, 아래:1 왼쪽:2, 오른쪽:3
        queue = deque([start])
        while queue:
            x,y,cost,d = queue.popleft()
            for idx,(dx,dy) in enumerate(direction):
                nx = x + dx
                ny = y + dy
                ncost = cost + 100 if d == idx else cost + 600
                if 0 <= nx < size and 0 <= ny < size and board[nx][ny] != 1 and table[nx][ny] > ncost:
                    table[nx][ny] = ncost
                    queue.append((nx,ny,ncost,idx))
        print(table)
        return table[-1][-1]
    return min(bfs((0,0,0,1)),bfs((0,0,0,3)))