[BOJ][C++] N-Queen

[BOJ][C++] N-Queen

 

문제

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

 

풀이

크기가 N X N인 체스판에 N개의 퀸을 공격할 수 없게 배치합니다. 저는 체스를 모르기 때문에 퀸의 이동 방향을 찾아보고 풀었습니다.

퀸의 공격 범위는 상, 하, 좌, 우, 대각선이 가능합니다. 즉, 퀸 하나를 배치하면 퀸이 있는 행과 열은 다른 퀸을 놓을 수 없습니다. 또한 대각선에도 놓을 수 없습니다. 그렇기 때문에 굳이 2차원 배열을 만들 필요 없이 1차원 배열에 퀸이 있는 row를 입력받으면 됩니다. 

하나의 col에는 하나의 퀸만 들어가야 하고 N만큼 for문을 돌면서 퀸을 놓고 앞서 놓은 퀸을 공격할 수 있는지 판단하면 됩니다. 앞서 놓은 퀸들을 공격할 수 없으면 재귀로 그 다음 퀸을 놓고 그렇지 않으면 놓았던 퀸을 다음 row에 놓아 볼 수 있도록 백트랙킹 합니다.

이 문제는 백트래킹의 기본 예제 문제라고 하네요. 기본인 만큼 탄탄히 익혀둬야겠어요.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <math.h>
using namespace std;
int N;
int res = 0;
int col[15];
bool isPossible(int q) {
    for (int i = 0; i < q; i++) {
        if (col[i] == col[q] || (q-i == abs(col[q]-col[i]))) {
            return false;
        }
    }

    return true;
}
void isQueen(int q) {
    if (q == N) {
        res += 1;
        return;
    }
    for (int i = 0; i < N; i++) {
        col[q] = i;
        if (isPossible(q)) {
            isQueen(q + 1);
        }
    }
}
int main() {
    scanf("%d", &N);
    isQueen(0);
    printf("%d", res);
}