사라지는 발판

MOVES = [[0, 1], [0, -1], [1, 0], [-1, 0]] INF = 1e9 def is_valid(board, loc): return 0 <= loc[0] < len(board) and \ 0 <= loc[1] < len(board[0]) and \ (board[loc[0]][loc[1]] != 0) def lost(board, loc): return board[loc[0]][loc[1]] == 0 or \ all(not is_valid(board, [loc[0] + r, loc[1] + c]) for r, c in MOVES) def copy(board): return [row[:] for row in board] def solve(board, aloc, bloc, turn, depth): if turn == 0 and lost(board, aloc): return 1, depth elif turn == 1 and lost(board, bloc): return 0, depth myloc = aloc if turn == 0 else bloc # 내가 이기는 결과라면 최소의 depth를 가져야 하고, # 내가 지는 결과라면 최대의 depth를 가져야 한다. min_depth, max_depth = INF, -1 for r, c in MOVES: # 새로운 board를 만든다. newboard = copy(board) newboard[myloc[0]][myloc[1]] = 0 # 새로운 위치를 만든다. newloc = [myloc[0] + r, myloc[1] + c] if not is_valid(newboard, newloc): continue new_aloc = newloc if turn == 0 else aloc new_bloc = bloc if turn == 0 else newloc winner, d = solve(newboard, new_aloc, new_bloc, 1-turn, depth+1) if winner == turn: min_depth = min(min_depth, d) else: max_depth = max(max_depth, d) if min_depth != INF: return turn, min_depth else: return 1-turn, max_depth def solution(board, aloc, bloc): winner, n_moves = solve(board, aloc, bloc, 0, 0) print(winner, n_moves) return n_moves