백준 9663 N-Queen C++

문제

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

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

입력

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

출력

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

 

풀이

체스판에서 퀸은 상하좌우 대각선으로 이동할 수 있다.

기존 퀸의 8가지 방향과 겹치지 않게 새로운 퀸을 놓아야 한다.

퀸이 배치될 수 있는지 보기 위해서는 기존 줄에 이미 놓여진 퀸이 있던가 대각선에 있다면 불가능하다. 

해당사항이 없으면 새로운 퀸이 놓여질 수 있다.

n개의 퀸을 다 놓으면 경우의 수를 1개 추가한다.

#include <iostream>
#include <cmath>

#define MAX 15 // 최대 MAX 수의 queen

using namespace std;

int board[MAX]; 
// board[i]는 i번째 행에 퀸이 몇번째 열에 있는지 의미하는 변수이다. (행열은 서로 바뀌어도 된다.)
// 즉 board[0] = 3일때, (1,4) 혹은 (4,1) 위치에 퀸이 있다는 뜻이다.
int n;
int cnt;

void path(int y) {
	// y는 현재 몇개의 퀸이 배치되었는지를 의미하는 변수다.
	int ko;
	if (y == n) {
		// n개의 퀸이 배치가 되었다면 이 경우는 답이다.
		cnt++;
		return;
	}
	for (int i = 0; i < n; i++) {
		// ko는 퀸이 배치될 수 있는지를 저장하는 플래그다.
		ko = 1;
		for (int j = 0; j < y; j++) {
			// 이미 배치가 끝난 퀸을 참고해서 i번째 칸에 퀸을 설치할 수 있는지를 확인한다.
			if (board[j] == i || abs(y - j) == abs(i - board[j])) {
				// j번째 줄에 있는 퀸과 같은 칸에 있거나, 대각선에 같은 곳에 있다면, i번째 칸에 대한 탐색을 중단한다.
				ko = 0;
				break;
			}
		}
		if (ko) {
			// 여기까지 왔다면 y번째 줄에 i번째 칸에 퀸을 놔두는 것이 가능하다.
			board[y] = i;
			path(y + 1);
		}
	}
}

int main() {

	//백준 9663 N-Queen
	//N*N 체스 판에서 N개의 Queen이 서로 공격하지 않을 경우의 수

	cin >> n;
	cnt = 0;
	path(0);

	cout << cnt << '\n';


	return 0;
}