[LeetCode 688] Knight Probability in Chessboard

688. Knight Probability in Chessboard

📌 문제 개념

• n x n 크기의 체스판에서 나이트가 (row, column) 위치에서 시작하여 정확히 k번 이동한다.
• 나이트는 한 번에 8가지 방향으로 이동 가능
• k번 이동 후 나이트가 체스판을 벗어나지 않을 확률을 반환해야한다.

제약 사항
- 1 <= n <= 25
- 0 <= k <= 100
💡 즉, k가 최대 100이므로 완전탐색은 불가능하고, DP를 활용해야 한다.

📌 접근 방식

1. Brute Force

• 나이트가 k번 이동하는 동안 모든 경로를 탐색
• k = 100이기에, O(8^100) 불가능한 풀이이다.

2. DP 적용

• dp배열을 활용해서 현재 위치에서 체스판을 벗어나지 않을 확률을 저장한다.
• dp배열을 설정하는 단계에서 실수를 해서 약간 헤메었는데, 같은 위치에 존재하더라도 몇 번 이동 했는지에 따라 확률 값이 달라질 수 있다.
  • ex) k가 3일때, 2번째 이동한 단계에서 (y,x) = (0,0)에 위치한 확률과, 1번째 이동 단계에서 (y,x) = (0,0)은 다르다.
• 즉 dp배열은 3차원 배열을 통해 dp[y][x][depth]로 설정이 되어야한다.
  • dp[y][x][depth] = depth 번의 이동동안 y, x에 도달할 수 있는 확률
• 해당 메모이제이션을 통해 O(n^2*k)로 시간 복잡도를 줄일 수 있다.

📌 풀이 설명

1. 방향 벡터 설정

int dy[8] = {2,1,-1,-2,-2,-1,1,2};
int dx[8] = {1,2,2,1,-1,-2,-2,-1};

• 나이트는 8가지 방향으로 이동 가능

2. DFS + DP 구현

double dfs(int y, int x, int n, int k, int depth, double total) {
    if(depth == k){
        dp[y][x][depth] = 1.0 / total;
        return 1.0 / total;
    }

    if(dp[y][x][depth] != -1){
        return dp[y][x][depth];
    }

    double temp = 0;

    for(int i= 0 ; i<8; i++){
        int py = y + dy[i];
        int px = x + dx[i];

        if(py < 0 || px < 0 || py >= n || px >= n){
            continue;
        }

        temp += dfs(py, px, n, k, depth+1, total);
    }

    dp[y][x][depth] = temp;

    return temp;
}

• depth == k이라면, 체스판 안에 존재하는 경우이므로 1/전체확률을 반환한다. (종료 조건)
• 만약 dp[y][x][depth]가 존재한다면 중복 계산을 방지한다.

📌 정답

class Solution {
public:
    int dy[8] = {2,1,-1,-2,-2,-1,1,2};
    int dx[8] = {1,2,2,1,-1,-2,-2,-1};
    double dp[26][26][101];

    double dfs(int y, int x, int n, int k, int depth, double total) {
        if(depth == k){
            dp[y][x][depth] = 1.0 / total;
            return 1.0 / total;
        }

        if(dp[y][x][depth] != -1){
            return dp[y][x][depth];
        }

        double temp = 0;

        for(int i=  0 ; i<8; i++){
            int py = y + dy[i];
            int px = x + dx[i];

            if(py < 0 || px <0 || py >= n || px >= n){
                continue;
            }

            temp += dfs(py,px,n,k,depth+1,total);
        }

        dp[y][x][depth] = temp;

        return temp;
    }

    double knightProbability(int n, int k, int row, int column) {
        for(int i= 0 ; i < 26; i++){
            for(int j= 0 ;  j<26; j++){
                for(int k = 0 ; k<101; k++){
                    dp[i][j][k] = -1;
                }
            }
        }

  
        return dfs(row, column, n, k ,0, pow(8,k));
    }
};