[Programmers] 경주로 건설 [ python, bfs ]

코딩테스트 연습 - 경주로 건설 | 프로그래머스 (programmers.co.kr)

def solution(board):
    answer = 0
	
    # 아래 방향으로 시작하는 경우
    down_x_dir = [-1, 1, 0, 0]
    down_y_dir = [0, 0, -1, 1]

    queue = []
    # 시작 x, 시작 y, 방향, 가격
    queue.append((0, 0, 1, 0))
    # x,y에 도착했을 때 turn해서 왔는지는 따로 저장
    price = [[[1e9 for _ in range(2)] for _ in range(len(board[0]))] for _ in range(len(board))]
    price[0][0][0] = 0
    price[0][0][1] = 0
    while queue:
        x, y, d, v = queue.pop(0)
        for i in range(4):
            nx = x + down_x_dir[i]
            ny = y + down_y_dir[i]
            if nx < 0 or ny < 0 or nx >= len(board) or ny >= len(board):
                continue
            if board[nx][ny] == 1:
                continue
            isturn = 0
            if i != d:
                isturn = 1
            value = v + 100
            if isturn:
                value += 500
            if price[nx][ny][isturn] < value:
                continue
            price[nx][ny][isturn] = value
            queue.append((nx, ny, i, value))
            
    # 오른쪽 방향으로 시작하는 경우
    right_x_dir = [0, 0, -1, 1]
    right_y_dir = [-1, 1, 0, 0]

    queue = []
    queue.append((0, 0, 1, 0))
    while queue:
        x, y, d, v = queue.pop(0)
        for i in range(4):
            nx = x + right_x_dir[i]
            ny = y + right_y_dir[i]
            if nx < 0 or ny < 0 or nx >= len(board) or ny >= len(board):
                continue
            if board[nx][ny] == 1:
                continue
            isturn = 0
            if i != d:
                isturn = 1
            value = v + 100
            if isturn:
                value += 500
            if price[nx][ny][isturn] < value:
                continue
            price[nx][ny][isturn] = value
            queue.append((nx, ny, i, value))

    answer = min(price[len(board)-1][len(board)-1][0], price[len(board)-1][len(board)-1][1])

    return answer