[파이썬] [BFS] Pro 경주로 건설

문제

https://programmers.co.kr/learn/courses/30/lessons/67259?language=python3 

코딩테스트 연습 - 경주로 건설

 

코드

from collections import deque
import sys
INF=sys.maxsize

def solution(board):
    def bfs(dire,cost,r,c):
        dx=[-1,1,0,0]
        dy=[0,0,-1,1]

        table=[[INF]*len(board) for _ in range(len(board))]

        queue=deque()
        queue.append((dire,cost,r,c))


        while queue:
            d,cost,r,c=queue.popleft()

            for i in range(4):
                nx=r+dx[i]
                ny=c+dy[i]

                if d!=i:
                    n_cost=cost+600
                else:
                    n_cost=cost+100
                if 0<=nx<len(board) and 0<=ny<len(board) and board[nx][ny]!=1 and table[nx][ny]>n_cost:
                    table[nx][ny]=n_cost
                    queue.append((i,n_cost,nx,ny))
        return table[-1][-1]
    return min(bfs(3,0,0,0),bfs(1,0,0,0))