boj 9663 N-Queen

 

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

9663번: N-Queen

 

백트래킹의 대표적인 문제입니다.

퀸은 가로, 세로, 대각선 방향으로 어디든 갈 수 있으므로 서로 공격하지 못하게 하려면 위와 같은 형태가 되어야합니다.

 

문제에서는 위와 같은 형태가 몇 개 나올 수 있는지 출력하는 문제입니다.

 

x을 1씩 올려가면서 dfs를 돌리고 x,y 위치에서 y방향, 대각선 방향의 위치에 다른 퀸이 놓여져 있는지 체크 후에 놓는 방식으로 하였습니다.

 

y방향을 열을 나타내고, 대각선 방향은 /, \방향이 있습니다.

우선 좌표가 이런식으로 되어있습니다.

 

y 좌표는 말 그대로 (x, y)에서 y좌표만 체크해주시면 되고

 

대각선좌표는 이런식입니다.

왼쪽은 /방향 (x + y)를 나타낸것이고, 오른쪽은 \방향 (x - y + N - 1)를 나타낸 것입니다.

 

각 방향에 말이 이미 놓여있는지 체크하고 놓여있지 않을때만 말을 놓아주도록 합니다.

 

 

#include <iostream>
using namespace std;
 
bool col[16], Left[27], Right[27];
int N, ans;
 
void dfs(int x) {
    if (x == N) {
        ans++;
        return;
    }
 
    for (int y = 0; y < N; y++) {
        if (col[y]) continue;
        if (Left[x + y] || Right[x - y + N - 1]) continue;
            col[y] = true;
            Left[x + y] = true;
            Right[x - y + N - 1] = true;
            dfs(x + 1);
            Right[x - y + N - 1] = false;
            Left[x + y] = false;
            col[y] = false;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    dfs(0);
    cout << ans << '\n';
 
    return 0;
}