[백준] 9663 N-Queen (C++)

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

문제 풀이

백트래킹(재귀)를 이용하여 풀었다. 백트래킹쪽에서 유명한 문제라고한다.

일차원 배열로 생각하면 더 단순해지고 속도도 빨라질수 있다는것을 알게 해준 문제였다.

일차원 배열의 인덱스를 level개념 (행) 그 안에 열을 넣었다.

 

또한 같은 대각선상에 있는지를 탐색할때 대각선위치이므로 abs(arr[level] - arr[i] ) 과 level - i 가 같은지 조건을걸어주면된다.

 

또한 arr[level] = i 로 넣어두고 check() 함수를 이용하자 check 를 먼저해버리면 전부 0이 들어가있으므로 다음순서로 넘어가지못한다(이것때문에 디버깅으로 시간좀 걸렸습니다 ㅠ)

 

 

소스 코드 

 

#include<iostream>
#include<vector>
using namespace std;
int N;
int cnt;
int arr[15];

bool check(int level) {

	for (int i = 0; i < level; i++) {
		if (arr[i] == arr[level] || abs(arr[level] - arr[i]) == level - i) //같은 행, 같은 열 ,대각선에 없으면 =true
			return false;
	}
	return true;
	}
void dfs(int level) {
	if (level == N) {
		cnt++;
		return;
	}
		for (int i = 0; i < N; i++) {
				arr[level] = i;
			if (check(level) == true) {
				dfs(level + 1);
				arr[level] = 0;
			}
		}
	

}
int main() {
	cin >> N;

	dfs(0);
	
	cout << cnt;

	return 0;
}