9663번 N-Queen

백트래킹 기법이 있다. 백트래킹은 기본적으로 부르트포스 기법을 응용한 것이다. 부르트포스처럼 계속 돌면서 특정 조건이면 그쪽으로는 더이상 뻗지 않는 것이다.
그래서 기본적으로 부르트포스로 코드를 짜고, if로 건너뛰게 해주자
평소에도 많이 사용하는 기법인데, 구체적인 조건(여기서는 퀸의 특징)을 잘활용해야 한다.
개인적으로는 함수를 많이 만드는 것을 좋아하지 않는다. 막상 시험장에서는 생각이 나지 않을 수 있을 것 같아서이다.

#include <iostream>

using namespace std;

int n, cnt=0;
int map[16][16];
int check(int row, int col) {
	//1. 일단 같은 col에 있나 확인
	for (int i = 0; i < row; i++) {
		if (map[i][col] == 1) return 0;
	}
	//2. 왼쪽 위 대각선에 있나 확인
	int x = row - 1;
	int y = col - 1;
	while (x >= 0 && y >= 0) {
		if (map[x][y] == 1) return 0;
		x -= 1;
		y -= 1;
	}
	//3. 오른쪽 위 대각선에 있나 확인
	x = row - 1;
	y = col + 1;
	while (x >= 0 && y < n) {
		if (map[x][y] == 1) return 0;
		x -= 1;
		y += 1;
	}
	return 1;
	
}

void DFS(int row) {
	if (row==n) {
		cnt++;
	}
	else {
		for (int i = 0; i < n; i++) {
			map[row][i] = 1;
			if (check(row, i) == 1) DFS(row+1);
			map[row][i] = 0;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	DFS(0);
	cout << cnt << '\n';
	return 0;
}