다른 사람 풀이
import math
from collections import deque
def solution(board):
def bfs(start):
# table[y][x] = 해당 위치에 도달하는 최솟값.
table = [[math.inf for _ in range(len(board))] for _ in range(len(board))]
# 진행 방향. 위 - 0, 왼쪽 - 1, 아래 = 2, 오른쪽 = 3
dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
queue = deque([start])
# 처음 위치의 비용 = 0
table[0][0] = 0
while queue:
# y좌표, x좌표, 비용, 진행방향
y, x, cost, head = queue.popleft()
for idx, (dy, dx) in enumerate(dirs):
ny, nx = y + dy, x + dx
# 진행방향과 다음 방향이 일치하면 + 100, 다르면 전환비용 500 + 진행비용 100 = 600
n_cost = cost + 600 if idx != head else cost + 100
# board[y][x] == 0 : 진행방향에 벽이 없음. table[ny][nx] > n_cost : 다음 좌표의 최솟값보다 진행방향 비용이 작을 경우
if 0 <= ny < len(board) and 0 <= nx < len(board) and board[ny][nx] == 0 and table[ny][nx] > n_cost:
# table 좌표 업데이트.
table[ny][nx] = n_cost
queue.append((ny, nx, n_cost, idx))
return table[-1][-1]
return min(bfs((0, 0, 0, 2)), bfs((0, 0, 0, 3)))처음에는 DFS로, 그 다음에는 가지치기를 한 (비용이 넘어가면 진행하지 않는) DFS로 하니 70점이 나왔다. 여기서 DFS+Dp로 하려다가 실패하고, BFS로 풀었다. BFS는 다른 사람들의 풀이와 거의 비슷한데 이유는 알 수 없지만 실패했다. 나중에 시간이 날때 다시 풀어야 겠다.
