백준 9663 [C++]

www.acmicpc.net/problem/9663

9663번: N-Queen

1. 풀이방법

 

- N개의 퀸을 놓을 수 있는 경우의 수 를 구하는 문제이고, 모든 경우의 수를 탐색하는데 시간을 신경써야합니다.

 

- 처음에는 그냥 dx[8],dy[8] 을 선언해서 8방향을 모두 탐색하다가 이미 다른 퀸이 있으면 리턴하고 라는 식으로

 

- 구현을 했다가.....N=5일때 까지 였나...? 까지 밖에 나오지 않았습니다...

 

- 처음에 N이 최대 14이길래 시간초과는 신경 안써도 되는 줄 알고 짰다가 당황한 문제였습니다.

 

- 체스판의 특성을 이용하여 x,y좌표의 특징들을 이용해서 놓을 수 있는지를 판단해야 했습니다.

 

 

 

 

 

2. 주의사항

 

- 체스판의 특성을 활용, 시간초과를 주의해야 함.

 

- 2차원 배열이 아닌 1차원배열을 이용하여 [x]=y를 통해 x,y 좌표를 나타내는 것이 처음에는 생소할 수 있음

 

 

 

 

3. 나의코드

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

int N;
int resultcount = 0;
int queenarr[15]; //[x]= y
 // 0~ N-1까지 사용
bool checking(int x, int y) {
	for (int i = 0; i < x; i++) {
		if ( abs(y-queenarr[i]) == abs(x -i) || queenarr[i] == y) {
			return false;
		}
	}
	return true;
}
void makecase(int x) {
	if (x == N) {
		resultcount++; return;
	}
	for (int i = 0; i < N; i++) {
		if (checking(x, i)) {
			queenarr[x] = i;
			makecase(x + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	makecase(0);
	cout << resultcount << "\n";
	return 0;
}