문제 링크
풀이 과정
전체 코드
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))])
Python
복사