C++로 서로 공격하지 않도록 K개의 나이트 배치하기

문제 개요

이 문제에서는 세 개의 정수 K, N, M이 주어지며, 우리의 과제는 NxM 크기의 체스판 위에 서로 공격하지 않도록 K개의 나이트를 배치하는 것입니다. 유효한 배치 방법이 존재하지 않는 경우도 있고, 여러 가지 배치가 가능한 경우도 있습니다. 이때 가능한 모든 유효한 배치를 출력해야 합니다.

나이트(Knight)는 체스 기물 중 하나로, 두 칸 앞으로 이동한 뒤 한 칸 왼쪽 또는 오른쪽으로 움직이는 말입니다. 체스판 위에서 어느 방향으로든 이동할 수 있습니다.

공격(Attack)은 한 기물이 유효한 수 중 하나를 두었을 때 다른 기물과 같은 위치에 도달할 수 있는 상태를 의미합니다.

예시를 통해 문제를 자세히 이해해 보겠습니다.

입력 − M = 3, N = 3, K = 5

출력 −

K A K
A K A
K A K

A K A
K K K
A K A

해결 접근 방법

이 문제를 해결하기 위해 각 행을 따라 열마다 나이트를 하나씩 차례대로 놓아가는 방식으로 시작합니다. 그리고 나이트를 배치할 때마다 공격받는 위치들을 확인합니다. 나이트를 놓기 전에 해당 위치가 안전한지 검사하고, 안전하다면 그곳에 배치한 뒤 다음 위치로 넘어갑니다.

모든 가능한 배치 조합을 얻기 위해 백트래킹(Backtracking) 기법을 사용합니다. 이를 위해 나이트를 하나 배치할 때마다 현재 보드 상태를 복사한 새로운 보드를 생성하여 재귀 호출에 활용함으로써, 이전 상태로 되돌아갈 수 있도록 합니다. 이러한 방식을 통해 모든 가능한 해답을 빠짐없이 탐색할 수 있습니다.

예시

위에서 설명한 해결 방법을 C++로 구현한 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;
int m, n, k, count = 0;
void displayPositions(char** board){
   cout<<endl;
   for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
         cout<<board[i][j]<<"\t";
      }
      cout<<endl;
   }
}
void canattack(int i, int j, char a,
char** board){
   if ((i + 2) < m && (j - 1) >= 0) {
      board[i + 2][j - 1] = a;
   }
   if ((i - 2) >= 0 && (j - 1) >= 0) {
      board[i - 2][j - 1] = a;
   }
   if ((i + 2) < m && (j + 1)< n) {
      board[i + 2][j + 1] = a;
   }
   if ((i - 2) >= 0 && (j + 1) < n) {
      board[i - 2][j + 1] = a;
   }
   if ((i + 1) < m && (j + 2) <n) {
      board[i + 1][j + 2] = a;
   }
   if ((i - 1) >= 0 && (j + 2) < n) {
      board[i - 1][j + 2] = a;
   }
   if ((i + 1) < m && (j - 2) >= 0) {
      board[i + 1][j - 2] = a;
   }
   if ((i - 1) >= 0 && (j - 2) >= 0) {
      board[i - 1][j - 2] = a;
   }
}
bool canPlace(int i, int j, char** board){
   if (board[i][j] == '_')
      return true;
   else
      return false;
}
void place(int i, int j, char k, char a,
char** board, char** new_board){
   for (int y = 0; y < m; y++) {
      for (int z = 0; z < n; z++) {
         new_board[y][z] = board[y][z];
      }
   }
   new_board[i][j] = k;
   canattack(i, j, a, new_board);
}
void placeKnights(int k, int sti, int stj, char** board){
   if (k == 0) {
      displayPositions(board);
      count++;
   } else {
      for (int i = sti; i < m; i++) {
         for (int j = stj; j < n; j++) {
            if (canPlace(i, j, board)) {
               char** new_board = new char*[m];
               for (int x = 0; x < m; x++) {
                  new_board[x] = new char[n];
               }
               place(i, j, 'K', 'A', board, new_board);
               placeKnights(k - 1, i, j, new_board);
            }
         }
         stj = 0;
      }
   }
}
int main() {
   m = 3, n = 3, k = 5;
   char** board = new char*[m];
   for (int i = 0; i < m; i++)
   board[i] = new char[n];
   for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++)
      board[i][j] = '_';
   }
   cout<<"The ways in which "<<k<<" knights can be placed in "<<m<<"x"<<n<<" chessboard are :\n";
   placeKnights(k, 0, 0, board);
   return 0;
}

출력

The ways in which 5 knights can be placed in 3x3 chessboard are :
K A K
A K A
K A K

A K A
K K K
A K A

출력 결과에서 나이트가 배치된 위치는 K로 표시되고, 해당 나이트에게 공격받는 위치는 A로 표시됩니다. 이처럼 백트래킹을 활용하면 주어진 체스판에서 서로 공격하지 않는 모든 나이트 배치 경우의 수를 체계적으로 찾아낼 수 있습니다.