[BOJ]백준 9663번: N-Queen

대표적인 백트래킹 문제인 N-Queen( https://www.acmicpc.net/problem/9663 )

9663번: N-Queen

크기가 N*N인 체스판에 퀸 N개를 서로 공격할 수 없게끔 놓을 수 있는 방법의 수를 구하는 문제

퀸이 무조건 N개가 놓여야 하기 때문에 같은 열이나 같은 행에는 절대 퀸이 같이 올 수 없다

이렇기 때문에 나는 move 함수와 func 함수를 만들었는데,

move 함수는 좌표를 인자로 넘겨받아 그 좌표에서의 퀸의 이동경로를 체크하고 이동가능한 칸의 수를 반환

func 함수는 각각의 행에서 퀸을 놓을 수 있는 모든 열의 경우의수를 체크하고 재귀호출을 진행한다

 

백트래킹에서 가장 중요한것은 재귀호출 타이밍과, 현재 경우의 수가 영향을 준 자료형이 있다면 초기화를 해주는 것이 중요!!

#include <cstdio>
#include <stack>
#define safe(x,y) x>=0&&x<n&&y>=0&&y<n
using namespace std;
int n, ans, sum, dx[] = { 1,0,-1,0,1,1,-1,-1 }, dy[] = { 0,1,0,-1,1,-1,-1,1 };
bool v[16][16], b;
struct point { int x, y; };
stack<point> s;
int move(point cur) {
	int q = 1;
	v[cur.y][cur.x] = 1;
	s.push({ cur.x,cur.y });
	for (int i = 0, nx, ny; i < 8; i++) {
		nx = cur.x + dx[i]; ny = cur.y + dy[i];
		while (safe(nx, ny)) {
			if (!v[ny][nx]) {
				s.push({ nx,ny });
				q++;
				v[ny][nx] = 1;
			}
			nx += dx[i]; ny += dy[i];
		}
	}
	return q;
}
void func(int dep) {
	if (dep == n)return;
	for (int i = 0, q; i < n; i++) {
		if (v[dep][i])continue;
		q = move({ i,dep });
		if (dep == n - 1 && s.size() == n * n)ans++;
		func(dep + 1);
		while (q--) {
			point p = s.top(); s.pop();
			v[p.y][p.x] = 0;
		}
	}
}
int main() {
	scanf("%d", &n);
	func(0);
	printf("%d", ans);
	return 0;
}