[swexpert] 2806. N-Queen (dfs, C++) [D3]

행을 이동하면서 각 열에 퀸을 놔본다.

 

#include <iostream>
#include <cstring>
using namespace std;

int t,n;
int col[11];// 각 행에 놓는 열의 위치를 저장한다
int cnt;

bool check(int row) {

	for (int i = 0; i < row; i++) {
		if (col[i] == col[row] || abs(col[row] - col[i]) == row - i) {// 기울기가 판단 
			return false;
		}
	}
	return true;
}

void queen(int row) {
	if (row == n) {//모든 퀸 다 놓음
		cnt += 1;
		return;
	}
	for (int j = 0; j < n; j++) {//놓을 열을 선택
		col[row] = j; //현재 ROW(열)에 j행에 놔본다
		if (check(row)) { //겹치는거 확인
			queen(row + 1); //안 겹치면 다음 행으로 이동
		}
		
	}
}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);


	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin >> n;
		cnt = 0;
		memset(col, false, sizeof col);
		queen(0);

		cout << "#" << tc << " " << cnt << "\n";
	}


	return 0;
}