N-Queen

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, ans=0;
bool isused1[40]; // y좌표가 평행한 경우들 검사
bool isused2[40]; // x+y와 기울기가 같은 경우들 검사
bool isused3[40]; // x-y와 기울기가 같은 경우들 검사 (음수 예방차 최대차이를 더해줌 --> +(n-1))
void func(int depth){
    if(depth == N) ans++;
    else{
        for(int i=0;i<N;i++)
        {
            /* y좌표와 평행 or x+y와 기울기가 같다 or x-y와 기울기가 같다
               --> 퀸이 움직일 수 있는 칸이 없다는 것! */
            if(isused1[i] or isused2[i+depth] or isused3[i-depth+(N-1)])
                continue;
            isused1[i] = 1;
            isused2[i+depth] = 1;
            isused3[i-depth+(N-1)] = 1;
            func(depth+1);
            isused1[i] = 0;
            isused2[i+depth] = 0;
            isused3[i-depth+(N-1)] = 0;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    func(0);
    cout << ans;
    return 0;
}

• 백트래킹의 대표적인 문제
  --> 해당문제를 완전탐색으로 하는 것보다 훨씬 효율적임
         (백트래킹은 조건을 만족하는 모든 경우를 돌기 때문)

• 문제 이해
  : 퀸은 같은 행/열/대각선 으로 이동할 수 있다.
  즉, 가능한 모든 경우는 한 행에 하나의 퀸이 있을 것이기 때문에
  하나의 행에 하나의 퀸을 배열하는 경우 중 이미 놓은 퀸의 이동범위와 겹치지 않는 경우를 찾아야 한다

• key point!
  : 퀸의 이동범위를 측정하기 위한 isused 배열 3개 사용
  (isused1[] / isused2[] /isused3[])
  
• isused1[]은 같은 행을 검사하기 위한 배열

• isused2[]는 x+y기울기가 같은지 검사하는 배열

• isused3[]는 x-y기울기가 같은지 검사하는 배열