NxN 크기의 체스판이 하나 주어지고, 나이트(기사)가 r행 c열에서 출발하여 정확히 K번 이동하려고 합니다. 행과 열은 0부터 시작하는 인덱스를 사용하므로, 좌측 상단 칸은 (0, 0), 우측 하단 칸은 (N-1, N-1)입니다.
나이트는 한 칸에서 총 8가지 방향으로 이동할 수 있으며, 그 이동 경로는 아래 다이어그램과 같습니다.
나이트는 이동할 때마다 8가지 가능한 이동 중 하나를 무작위로 선택합니다. 나이트는 정확히 K번 이동을 마치거나 체스판 밖으로 벗어날 때까지 계속 움직입니다. 우리가 구해야 하는 것은 나이트가 이동을 멈췄을 때 여전히 체스판 위에 남아 있을 확률입니다.
예를 들어 입력이 N=3, K=2, r=0, c=0이라면 출력은 0.0625가 됩니다. 그 이유는 첫 번째 이동에서 체스판에 남아 있는 경우의 수가 두 가지((1,2), (2,1))뿐이고, 각 위치에서도 체스판에 머무는 이동이 두 가지씩 존재하기 때문입니다. 따라서 나이트가 체스판에 남아 있을 총 확률은 0.0625가 됩니다.
문제 해결 접근 방법
이 문제는 재귀 호출과 메모이제이션(Memoization)을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- 8가지 이동 방향을 담은 배열 dir을 정의합니다: [[-2,-1], [-2,1], [2,-1], [2,1], [1,2], [1,-2], [-1,2], [-1,-2]]
- x, y, n, k, 그리고 3차원 배열 dp를 인자로 받는 재귀 함수 solve()를 정의합니다.
- 만약 x >= n 또는 y >= n 또는 x < 0 또는 y < 0이라면(체스판 밖), 0을 반환합니다.
- k가 0이면(모든 이동 완료), 1을 반환합니다.
- dp[k][x][y]가 -1이 아니라면(이미 계산된 값), 해당 값을 반환합니다.
- dp[k][x][y]를 0으로 초기화합니다.
- i를 0부터 7까지 반복하면서 dp[k][x][y] += solve(x+dir[i][0], y+dir[i][1], n, k-1, dp)를 누적합니다.
- dp[k][x][y]를 반환합니다.
메인 함수에서는 다음 작업을 수행합니다.
- (K+1) x N x N 크기의 3차원 배열을 생성하고 모든 값을 -1로 초기화합니다.
- solve(r, c, N, K, dp) / 8^K를 반환합니다. 전체 경우의 수는 각 이동마다 8가지이므로 8^K가 됩니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
class Solution {
public:
double solve(int x, int y, int n, int k, vector < vector < vector < double > > >& dp){
if(x >= n || y >= n || x < 0 || y < 0 ) return 0.0;
if(k == 0) return 1.0;
if(dp[k][x][y] != -1) return dp[k][x][y];
dp[k][x][y] = 0;
for(int i = 0; i < 8; i++){
dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp);
}
return dp[k][x][y];
}
double knightProbability(int N, int K, int r, int c) {
vector < vector < vector < double > > > dp (K + 1, vector < vector < double > >(N, vector < double >(N, -1))) ;
return solve(r, c, N, K, dp) / pow(8, K);
}
};
main(){
Solution ob;
cout << (ob.knightProbability(3, 2, 0, 0));
}입력
3 2 0 0
출력
0.0625