[백준/C++] 9663번: N-Queen (DFS, 백트랙킹)

 

1) 기본가정: 같은 행에 Queen을 놓지 않는다.

2) 유망한 노드인지 확인하는 함수

    - 같은 열이나 같은 대각선에 놓이는지 확인 -> 해당되면 유망하지 x

    - 같은 열 체크: col[i] == col[j]

    - 같은 대각선 체크: abs(col[i]-col[j]) == i-j

 

#include<iostream>
using namespace std;

int col[15];
int N;
int cnt = 0;

bool promising(int i) {
	for (int j = 0; j < i; j++) {
		if (col[j] == col[i] || abs(col[i] - col[j]) == (i - j)) return false;
	}
	return true;
}


void dfs(int i) { //i는 놓은 queen의 수이기도 하면서 행을 뜻한다.
	if (i == N) cnt++;
	else {
		for (int j = 0; j < N; j++) {
			col[i] = j;
			if (promising(i)) dfs(i + 1);
		}
	}
}


int main() {

	cin >> N;

	dfs(0);

	cout << cnt;

	return 0;
}