이 문제에서는 m×n 크기의 체스판이 주어지며, 기물이 놓여 있는 위치는 1로 표시됩니다. 즉, board[i][j] = 1이면 해당 칸에 기물이 존재하는 것이죠. 그리고 나이트의 시작 위치가 주어졌을 때, 모든 기물이 같은 색이라고 가정하므로(즉, 공격이 일어나지 않는 상황) 체스판 위에서 나이트가 이동할 수 있는 총 경우의 수를 구하는 것이 우리의 과제입니다.
체스에서 나이트의 이동 방식
나이트(Knight)는 체스에서 특수한 방식으로 움직이는 기물입니다. 나이트의 이동 규칙은 다음과 같습니다.
- 수평으로 두 칸, 수직으로 한 칸 이동
- 수직으로 두 칸, 수평으로 한 칸 이동
문제 이해를 위한 예시
예제를 통해 문제를 살펴보겠습니다.
입력 −
board[][] = {
{ 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }
};
Position : (1,1)출력 − 4
해결 방법
이 문제를 해결하려면 나이트가 이동할 수 있는 모든 후보 위치 중에서 실제로 유효한 이동만 골라내야 합니다. 어떤 이동이 유효하려면 다음 조건을 만족해야 합니다.
- 이동한 위치가 체스판 범위 안에 있어야 합니다.
- 이동한 위치에 다른 기물이 이미 놓여 있지 않아야 합니다.
이를 위해 먼저 현재 위치에서 나이트가 이동할 수 있는 8가지 후보 좌표를 모두 생성합니다. 그다음 각 이동이 위의 유효성 조건을 만족하는지 검사하고, 유효한 이동일 때마다 카운트를 증가시킵니다. 최종적으로 카운트된 값이 바로 해당 위치에서 나이트가 이동할 수 있는 총 횟수가 됩니다.
구현 예제
위 해결 방법을 C++로 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
#define N 8
#define M 8
using namespace std;
int countPossibleMoves(int mat[N][M], int p, int q){
int Xmoves[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int Ymoves[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int count = 0;
for (int i = 0; i < 8; i++) {
int x = p + Xmoves[i];
int y = q + Ymoves[i];
if (x>=0 && y>=0 && x<N && y<M && mat[x][y]==0)
count++;
}
return count;
}
int main(){
int mat[N][M] = { { 0, 1, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 0 },
{ 0, 0, 0, 1 }};
int position[2] = {1,1};
cout<<"Total number of moves possible for Knight from position ("<<position[0]<<" , "<<position[1]<<") are : ";
cout<<countPossibleMoves(mat, position[0], position[1]);
return 0;
}실행 결과
Total number of moves possible for Knight from position (1 , 1) are : 4
위 코드에서 Xmoves와 Ymoves 배열은 나이트가 이동할 수 있는 8가지 방향의 상대적 좌표 변화량을 나타냅니다. 반복문을 통해 각 방향으로 이동했을 때의 새로운 좌표(x, y)를 계산하고, 해당 좌표가 체스판 내부에 있으면서 동시에 비어 있는 칸(mat[x][y] == 0)인 경우에만 카운트를 증가시킵니다. 이처럼 단순한 배열 순회와 조건 검사만으로도 나이트의 유효 이동 횟수를 효율적으로 계산할 수 있습니다.