이 튜토리얼에서는 변형 나이트(Modified Knight)가 도달할 수 있는 위치의 개수를 구하는 C++ 프로그램을 다룹니다.
8×8 크기의 체스판과 시작 위치, 그리고 이동 횟수(steps)가 주어졌을 때, 정확히 주어진 횟수만큼 이동한 후 변형 나이트가 도달할 수 있는 서로 다른 칸의 개수를 계산하는 것이 목표입니다.
변형 나이트란?
일반적인 체스 나이트는 8가지 방향으로만 움직일 수 있지만, 변형 나이트는 여기에 대각선으로 인접한 칸으로의 이동까지 포함해 총 12가지 방향으로 이동할 수 있습니다. 즉, 기존 나이트의 L자 움직임에 상하좌우 대각선 한 칸 이동이 추가된 형태입니다.
접근 방법
- 현재 위치에서 시작해 재귀적으로 12가지 방향을 모두 탐색합니다.
- 체스판의 경계를 벗어나거나 허용된 이동 횟수를 초과하면 해당 경로의 탐색을 중단합니다(백트래킹).
- 정확히 steps번 이동한 시점에 도달한 위치를 visited 배열에 기록합니다.
- 탐색이 끝난 후 visited 배열에서 방문 표시(값이 1)된 칸의 개수를 세어 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 도달 가능한 위치를 찾는 함수
void findSteps(int current_row, int current_column,int curr, int board_size, int steps,int* visited){
// 경계 검사
if (current_row >= board_size || current_row < 0
|| current_column >= board_size || current_column < 0
|| curr > steps) {
return;
}
if (curr == steps) {
*((visited + (current_row)*board_size) + current_column) = 1;
return;
}
findSteps(current_row - 2, current_column - 1,curr + 1, board_size, steps, visited);
findSteps(current_row - 2, current_column + 1,curr + 1, board_size, steps, visited);
findSteps(current_row - 1, current_column - 2,curr + 1, board_size, steps, visited);
findSteps(current_row - 1, current_column - 1,curr + 1, board_size, steps, visited);
findSteps(current_row - 1, current_column + 1,curr + 1, board_size, steps, visited);
findSteps(current_row - 1, current_column + 2,curr + 1, board_size, steps, visited);
findSteps(current_row + 1, current_column - 2,curr + 1, board_size, steps, visited);
findSteps(current_row + 1, current_column - 1,curr + 1, board_size, steps, visited);
findSteps(current_row + 1, current_column + 1,curr + 1, board_size, steps, visited);
findSteps(current_row + 1, current_column + 2,curr + 1, board_size, steps, visited);
findSteps(current_row + 2, current_column - 1,curr + 1, board_size, steps, visited);
findSteps(current_row + 2, current_column + 1,curr + 1, board_size, steps, visited);
return;
}
int countSteps(int current_row, int current_column,int board_size, int steps){
int visited[board_size][board_size];
for (int i = 0; i < board_size; i++) {
for (int j = 0; j < board_size; j++) {
visited[i][j] = 0;
}
}
int answer = 0;
findSteps(current_row, current_column, 0,board_size, steps, (int*)visited);
for (int i = 0; i < board_size; i++) {
for (int j = 0; j < board_size; j++) {
if (visited[i][j] == 1) {
answer++;
}
}
}
return answer;
}
int main(){
int board_size = 8, steps = 1;
int current_row = 4, current_column = 4;
cout << countSteps(current_row, current_column,board_size, steps);
return 0;
}출력 결과
12
코드 설명
findSteps() 함수는 재귀 호출을 통해 현재 위치에서 이동 가능한 12개 방향을 모두 탐색합니다. 먼저 경계 검사를 수행하여 체스판을 벗어나거나 이동 횟수를 초과한 경우 즉시 종료함으로써 불필요한 연산을 줄입니다. 이동 횟수가 정확히 steps에 도달하면 해당 좌표를 visited 배열에 1로 표시합니다.
countSteps() 함수는 visited 배열을 0으로 초기화한 뒤 탐색을 시작하고, 탐색이 완료되면 배열 전체를 순회하며 도달 가능한 칸(값이 1)의 개수를 세어 반환합니다.
위 예제에서는 8×8 체스판의 중앙인 (4, 4)에서 1번 이동했을 때의 결과를 구하며, 출력은 12입니다. 이는 변형 나이트가 한 번의 이동으로 도달할 수 있는 12개의 모든 칸이 판 내부에 있다는 의미입니다.
복잡도 분석
매 단계마다 최대 12개의 분기가 발생하므로 시간 복잡도는 이동 횟수에 대해 지수적으로 증가하며, 대략 O(12steps)입니다. 공간 복잡도는 체스판 크기에 비례하여 O(N²)입니다. 이동 횟수가 커질 경우 메모이제이션(Memoization)이나 동적 계획법(DP)을 적용하면 성능을 크게 개선할 수 있습니다.