문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

• 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

해결방법 및 소스코드

• Brute Force하게 재귀호출을 이용한 백트래킹 방법을 이용하였다.
• 이 문제를 처음 C로 풀었었을 때는 체스판을 2차원 배열로 만들어서 복잡하게 해결했었는데, 이번에는 1차원 배열만으로 해결했다.
• 굳이 복잡하게 2차원 배열을 만들 필요 없이, 1차원 배열의 인덱스(i)를 행(level), 각 원소(chessBoard[i])를 열로 생각하면 된다.
• 1차원 배열의 인덱스도 적절하게 활용하면 코드를 쉽고 간단하게 짤 수 있다는 것을 알게 해 준 문제였다.

#include <iostream> using namespace std; int N; //checkPosition: 현재 칸에 퀸을 놓을 수 있는지를 판단한다. //curlevel: 현재 퀸을 놓으려는 행번호 //curcol: 현재 퀸을 놓으려는 열번호 int checkPosition(int chessBoard[], int curlevel, int curcol) { //현재 놓으려는 칸의 열이 이전 퀸들과 중복이 있다면 놓을 수 없다. for (int i = 0; i < curlevel; i++) { if (chessBoard[i] == curcol) return 0; } //현재 놓으려는 칸의 이전 퀸들의 대각위치에 있다면 놓을 수 없다. //이전칸 (i, chessBoard[i])과 현재 놓으려는 칸 (curlevel, curcol)에서 x좌표의 차와 y좌표의 차가 같으면 대각위치이다. //즉, 두 점을 이은 직선의 기울기의 절대값이 1이면 놓을 수 없다. for (int i = 0; i < curlevel; i++) { if (abs(curlevel - i) == abs(curcol - chessBoard[i])) return 0; } return 1; } void placeQueen(int chessBoard[], int level, int &count) { //탈출 조건(count 증가 조건) if (level == N) count++; //chessBoard[현재레벨][x]에 퀸을 놓을 수 있는지 검사 for (int x = 0; x < N; x++) { //만약 퀸을 놓을 수 있다면, 퀸을 놓고 다음 단계로 이동. if (checkPosition(chessBoard, level, x)) { chessBoard[level] = x; placeQueen(chessBoard, level + 1, count); } } } int main() { cin >> N; //level: 체스판의 재귀 깊이 //count: 구하는 경우의 수를 카운트 int level = 0; int count = 0; //체스판 배열에서 각 인덱스는 '행', 각 원소는 '열'을 의미한다. int chessBoard[N]; placeQueen(chessBoard, level, count); cout << count; }