import heapq
from collections import deque
def solution(board):
n = len(board)
# ์, ์ฐ, ํ, ์ข
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cost_board = [[[float('inf')] * 4 for _ in range(n)] for _ in range(n)]
# ์ฐ์ ์์ ํ ์ฌ์ฉ
queue = []
heapq.heappush(queue, (0, 0, 0, -1)) # ๋น์ฉ์ ๋งจ ์์ ๋์ด ์ฐ์ ์์ ๊ฒฐ์
while queue:
cost, h, w, direction = heapq.heappop(queue)
for d, (dh, dw) in enumerate(directions):
h_new, w_new = h + dh, w + dw
if direction != -1 and d == (direction + 2) % 4: continue # ์ญ์ฃผํ
if 0 <= h_new < n and 0 <= w_new < n and board[h_new][w_new] == 0:
cost_new = cost + 100
if direction != -1 and direction != d:
cost_new += 500
if cost_new <= cost_board[h_new][w_new][d]:
cost_board[h_new][w_new][d] = cost_new
heapq.heappush(queue, (cost_new, h_new, w_new, d))
return min(cost_board[n - 1][n - 1])