백준 9663 (C++) N-Queen

탐색 종료의 기준을 잡는다.

내가 짠 코드는 어떤 행의 모든 열을 우선적으로 탐색하기 때문에 행이 n(체스판의 크기)가 되었을때 종료한다.

어떤 열 i, 어떤 행 j에 있다고 하자.

그 좌표를 기준으로 같은 열, 대각선에 위치하지 않으면 그 좌표를 체크해준다.

이 과정을 반복해서 종료조건에 도달했을 경우 가능한 체스판 경우를 +1해준다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 40

int n;
int cnt = 0;
bool isused1[MAX]; // 같은 열
bool isused2[MAX]; // 우상 대각
bool isused3[MAX]; // 좌상 대각

/* i는 열, j는 행 */
void solve(int j) {
    if(j == n) {
        cnt++;
        return;
    }
    for(int i = 0; i < n; i++) {
        if(isused1[i] || isused2[i + j] || isused3[i - j + n - 1]) continue;
        isused1[i] = true;
        isused2[i + j] = true;
        isused3[i - j + n - 1] = true;
        solve(j + 1); // 다음 행으로 넘어감
        isused1[i] = false;
        isused2[i + j] = false;
        isused3[i - j + n - 1] = false;
    }
}

int main() { // 8*8 의 최댓값: 64
    cin >> n;
    solve(0);
    cout << cnt;

    return 0;
}