문제 링크

풀이 과정

전체 코드

from collections import deque

def _isin_boundary(y, x, rows, cols):
    return (0 <= x < cols) and (0 <= y < rows)

def isPossible(y, x, rows, cols, board):
    return _isin_boundary(y, x, rows, cols) and board[y][x] == 0

def solution(board):
    def bfs(start):
        row_len, col_len = len(board), len(board[0])
        direction = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}  # 북, 동, 남, 서
        dp_table = [[1e+9 for _ in range(col_len)] for _ in range(row_len)]
        dp_table[0][0] = 0

        q = deque([start])   # y, x, cost, direction
        while q:
            y, x, c, d = q.popleft()
            for i in range(4):
                ny = y + direction[i][0]
                nx = x + direction[i][1]
                if isPossible(ny, nx, row_len, col_len, board):
                    # 진행 방향이 일치하는 경우(직선)에만 100원을 추가
                    nc = c+100 if i == d else c+600
                    if nc < dp_table[ny][nx]:
                        dp_table[ny][nx] = nc
                        q.append([ny, nx, nc, i])
                        
        return dp_table[-1][-1]
    
    return min([bfs((0, 0, 0, 1)), bfs((0, 0, 0, 2))])