백준 9663번 : N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

 문제 설명  

 

N이 주어졌을때 NxN 체스판에 N개의 퀸이 서로 공격할수없게 놓을수 있는 경우의 수.

 

 알고리즘 

 

재귀로 구현.

1. 가로는 검사 하지않고 세로만 검사하면된다. ( idx 가 1씩 증가하므로 굳이 가로는 검사하지않아도됨 ) 

2. 그러므로 배열을 1차원 배열로 진행가능 

3. 대각선검사는 만약 같은 대각선 위에 있다면 |행-열| 의 값이 항상 일정하므로 이것을 이용하면 된다.

 

(2차원배열로해야되는줄알고 30분동안 하다가 떄려침)

 

 코드 

 

#include<iostream>
#include<cmath>
 
using namespace std;
 
int N, sum=0;
int arr[16];
 
 
bool pos(int idx) {
    for (int i = 0; i < idx; i++) {
        if(arr[i]==arr[idx]||abs(arr[idx]-arr[i])==idx-i) return false;//대각선 검사 함수 
    }
    return true;
}
 
 
void DFS(int idx) {
    if (idx == N) {
        sum++;
        return;
    }
    for (int i = 0; i < N; i++) {
        arr[idx] = i;
        if (pos(idx) == true) DFS(idx + 1);
    }
 
 
}
int main() {
    cin >> N;
    DFS(0);
    cout << sum;
}