Leetcode 688. Knight Probability in Chessboard with Python

문제

On an n x n chessboard, a knight starts at the cell (row, column) 
and attempts to make exactly k moves. 
The rows and columns are 0-indexed, 
so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).

A chess knight has eight possible moves it can make, as illustrated below. 
Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

Each time the knight is to move, 
it chooses one of eight possible moves uniformly at random 
(even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

체스보드에 나이트가 있습니다.
체스보드의 크기는 n으로 주어지며 각 cell의 index는 0부터 시작합니다.
나이트의 위치는 row와 column으로 주어집니다.
나이트는 위 그림과 같은 8방향으로 전진할수 있으며, 총 k번 전진합니다.
나이트가 체스판에서 k번 전진했을때 떨어지지 않고 남아 있을 확률을 리턴하세요

예시

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: 나이트가 첫번째 이동했을때 살아 남을 가능성은 2 / 8, 두번째 이동했을때 살아 남을 가능성은 2 / 8이기에 둘을 곱해 0.0625가 된다.

제한

• 1 <= n <= 25
• 0 <= k <= 100
• 0 <= row, column <= n - 1

풀이

3차원 배열 board를 만드는데

이 board에 k번 이동이 남았을때 row와 col에서 이동시 살아남을 확률을 memoization 한다.

마지막 이동의 경우는 미리 전수조사하여 적어 놓는다.

def knightMoves(n: int, row: int, col: int):
    mx = [-2, -2, 2, 2, 1, -1, 1, -1]
    my = [-1, 1, -1, 1, -2, -2, 2, 2] 
    cnt = 0
    for i in range(8):
        tx = row + mx[i]
        ty = col + my[i]
        if tx >= 0 and tx < n and ty >= 0 and ty < n: cnt += 1
    return cnt

def knightProb(n, k, row, col, board, turn = 8):
    if k == 0: return 1.0

    # memoization 되어 있는 확률
    if k != 1 and board[k][row][col] != 0:
        return board[k][row][col]

    mx = [-2, -2, 2, 2, 1, -1, 1, -1]
    my = [-1, 1, -1, 1, -2, -2, 2, 2]

    # 마지막 자리일떄 확률
    if k == 1:
        return board[k][row][col] / turn

    prob = 0
    for i in range(8):
        tx = row + mx[i]
        ty = col + my[i]
        if tx >= 0 and tx < n and ty >= 0 and ty < n: prob += knightProb(n, k-1, tx, ty, board, turn * 8)
    board[k][row][col] = prob
    return board[k][row][col]



class Solution:
    def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
        board = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(101)]
        for i in range(len(board[0])):
            for j in range(len(board[0][0])):
                board[1][i][j] = knightMoves(n, i, j)

        return knightProb(n, k, row, column, board)