Daily LeetCode Challenge - 688. Knight Probability in Chessboard

Problem From.

https://leetcode.com/problems/knight-probability-in-chessboard/

오늘 문제는 체스판에서 knight 가 움직일때, 각각의 랜덤한 움직임으로 체스말이 체스판에 남아있는지 보는 문제였다.

이 문제는 dp 를 이용해서 풀 수 있었는데, 먼저 각각의 움직임을 지정해줄 pair array 를 만들고, 그 pair array 를 반복해주면서, 각각의 움직임을 기록해나간다. 기록해나간 움직임을 dp 로 불러와서 반복해주면서, 몇개의 경우의 수에 남아있는지 보면 되었다.

class Solution {
    fun knightProbability(N: Int, K: Int, r: Int, c: Int): Double {
        var probabilities = Array(N) { DoubleArray(N) { 1.0 } }
        val steps = listOf(Pair(-1, 2), Pair(1, 2), Pair(2, 1), Pair(2, -1), Pair(1, -2), Pair(-1, -2), Pair(-2, -1),
                Pair(-2, 1))
        for (k in 1..K) {
            val newProbabilities = Array(N) { DoubleArray(N) }
            for (fromR in 0 until N) {
                for (fromC in 0 until N) {
                    for (step in steps) {
                        val toR = fromR + step.first
                        val toC = fromC + step.second
                        if (toR in 0 until N && toC in 0 until N) {
                            newProbabilities[fromR][fromC] += 1.0 / 8 * probabilities[toR][toC]
                        }
                    }
                }
            }
            probabilities = newProbabilities
        }
        return probabilities[r][c]
    }
}