3520 : 체커 도전 (N-Queen Problem)

안녕하세요! 오늘은 체스에서 퀸을 배치하는 문제를 해결하는 방법에 대해 알아보겠습니다. 이 문제는 주어진 체스판의 크기 N에 대해 가능한 모든 퀸의 배치 개수를 구하는 것이 목표입니다. 예시를 통해 문제를 이해하고, 해결하는 방법을 알아보겠습니다.

---

문제 설명

체스에서 퀸(queen)은 가로, 세로, 대각선에 같은 퀸을 배치하지 못한다.

각 체커는 각 행에 1개, 각 열에 1개씩 밖에 배치할 수 없다. 

6*6체커보드에서 6개의 체커들은 다음과 같이 퀸을 배치할 수 있다.

	1	2	3	4	5	6
1		Q
2				Q
3						Q
4	Q
5			Q
6					Q

이 상태의 열 번호는 2 4 6 1 3 5로 나타낼 수 있다.

체스판의 크기가 N이 주어질 때, 퀸을 놓을 수 있는 모든 배치의 개수를 구하시오.

입력

체스판의 크기 N이 입력된다( 6 <= N <= 13 )

출력

처음 세 줄은 가능한 해법 3가지를 출력한다. 이때 열번호가 적은 순서부터 오름차순으로 세 가지만 출력한다.

네째 줄에 가능한 퀸의 배치 개수를 출력한다.

입력예시

6

출력예시

2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4

---

문제 해결 방법
이 문제를 해결하기 위해서는 재귀 함수를 활용하는 방법이 적합합니다. 주어진 체스판의 크기 N에 해당하는 퀸의 배치를 구하기 위해 재귀 함수를 호출하고, 가능한 모든 배치를 탐색합니다. 이때, 배치된 퀸이 서로 충돌하지 않도록 규칙을 확인하여 올바른 배치를 찾아야 합니다.

코드 설계
아래는 코드 설계(분석) 알고리즘을 자필로 작성한 이미지입니다.

#include <stdio.h>
int a, s[15], d, g;

// 퀸 배치가 가능한지 확인하는 함수
int isSafe(int row, int col)
{
   for (int i = 0; i < row; i++)
   {
      // 같은 열에 퀸이 있는 경우
      if (s[i] == col + 1)
         return 0;
      
      // 대각선 방향에 퀸이 있는 경우
      if (s[i] - i == col - row + 1 || s[i] - col == row - i + 1)
         return 0;
   }
   
   return 1;  // 퀸 배치 가능한 경우
}

// 재귀 함수를 통해 퀸의 배치를 탐색하는 함수
void placeQueens(int row)
{
   if (row == a)
   {
      d++;  // 가능한 퀸 배치의 개수 증가
      if (g < a * 3)
      {
         for (int i = 0; i < a; i++)
         {
            printf("%d ", s[i]);  // 퀸의 위치 출력
            g++;
         }
         printf("\n");
      }
      return;
   }
   
   for (int col = 0; col < a; col++)
   {
      if (isSafe(row, col))
      {
         s[row] = col + 1;  // 퀸 배치
         placeQueens(row + 1);  // 다음 행으로 이동하여 재귀 호출
      }
   }
}

// 메인 함수
int main()
{
   scanf("%d", &a);
   placeQueens(0);  // 첫 번째 행부터 퀸의 배치 시작
   printf("%d", d);  // 가능한 퀸 배치의 개수 출력

   return 0;
}

 

이 코드는 입력으로 체스판의 크기 N을 받고, 재귀 함수를 통해 가능한 퀸의 배치를 탐색하는 방식으로 문제를 해결합니다. 코드에서 사용된 주요 함수와 변수에 대해 간단히 설명하겠습니다.

f2: 퀸이 배치될 수 있는지 확인하는 함수입니다. 현재 배치된 퀸과 충돌하지 않는지 확인하고, 가능한 경우 1을 반환합니다.
f: 재귀 함수로, 퀸의 배치를 탐색하고 올바른 배치를 찾으면 개수를 증가시키고 출력합니다.
a: 체스판의 크기를 저장하는 변수입니다.
s: 퀸의 배치를 저장하는 배열입니다.
d: 올바른 퀸의 배치 개수를 저장하는 변수입니다.
g: 출력할 퀸의 배치 개수를 제한하기 위한 변수입니다.

---

오류 해결 과정
처음에는 퀸의 배치 위치와 배치 가능 여부를 한번에 한 재귀함수에서 진행햇는데 이게 코드가 꼬여 버리는 오류가 발생해버렸습니다/. 그래서 함수를 두개로 나누어 해결하였습니다.

위 코드를 실행하면 입력으로 주어진 체스판의 크기에 따른 가능한 퀸의 배치와 배치 개수를 출력합니다.
실행 화면

여기까지 체스판에서 퀸 배치하기 문제를 해결하는 방법에 대해 알아보았습니다. 퀸 배치 문제는 재귀 함수와 조건 확인을 통해 가능한 모든 배치를 탐색하는 방식으로 해결할 수 있습니다. 감사합니다 후 정융탐에서 보아요