[C++][백준] 9963번 N-Queen :: seoftware

 

---

 

소스코드

---

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

int N;
int answer;
int queen[15][15];
//퀸이 (x, y)에 영향을 미칠 수 있는지 확인
//x+1 은 퀸의 개수(cnt)와 같다
bool isAvailable(int x, int y) {
	int i, j;
	//y와 같은 세로축에 퀸 있으면 false
	for (i = 0; i < x; i++) {
		if (queen[i][y]) return false;
	}
	//대각선
	for (i = x - 1, j = y - 1; j >= 0 && i >= 0; i--, j--) {
		if (queen[i][j]) return false;
	}
	for (i = x - 1, j = y + 1; j < N && i >= 0; i--, j++) {
		if (queen[i][j]) return false;
	}
	return true;
}

void dfs(int cnt) {
	if (cnt == N) {
		answer++; return;
	}
	//cnt는 행, i는 열
	for (int i = 0; i < N; i++) {
		//내 자리에 퀸이 없고, 그 자리가 퀸이 가능한 자리인지 확인
		if (cnt < N &&!queen[cnt][i] && isAvailable(cnt, i)) {
			queen[cnt][i] = true; //가능하면 퀸을 그 자리에 놓고 다음열 dfs
			dfs(cnt + 1); //아랫줄에 퀸 놓을 자리 찾기
			queen[cnt][i] = false;
		}
	}
}
int main(void) {
	cin >> N;
	dfs(0);
	cout << answer << endl;
}

 

문제 접근 :

1. 퀸의 가로, 세로, 대각선에는 다른 퀸이 올 수 없다 = 한 줄에 퀸 하나

2. x축에 퀸을 하나 놓고, (x+1)줄에 퀸을 놓을 수 있는 자리를 찾는다. 

3. 마지막 줄(N-1)에 퀸을 놓고 나면 answer을 +1 해준다.