[C++] BOJ 9663 / 백트래킹 (N-Queen, 2차원 배열 속 대각선 계산)

문제 분석

 

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

크기가 N X N 인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 출력하는 문제이다.

체스 말에서의 퀸은 대각선을 포함한 상하좌우로 여러 칸 이동 가능하다.

 

해결 방법

퀸을 행 별로 하나 씩 배치하면서, 만나지 않는 경우를 전부 찾아야 하므로 백트래킹을 사용해야한다.

행 별로 하나 씩 두기 때문에, 같은 행에 있는지는 체크 하지 않아도 되지만, 같은 열에 있는지와 우측 대각선 좌측 대각선에 있는지 체크하기 위해 배열을 3개 사용해야한다.

같은 대각선에 있음을 확인하는 방법은, x+y가 같으면 좌측하단에서 우측상단을 잇는 대각선에 위치해있다.

반대로 좌측상단에서 우측하단을 잇는 대각선은 x-y가 같은지 확인하면 된다.

코드를 보면 알겠지만, x-y가 음수가 되면, 배열의 음수 인덱스는 없으므로 "n-1"를 더해주었다.

 

코드

#include <iostream>
using namespace std;

int n;
int board[15][15];
bool chk[15];
bool chk2[27];
bool chk3[27];
int cnt=0;
void queen(int q) {
    if(q==n) {
        cnt++;
        return;
    }
    for(int i=0;i<n;i++) {
        if(chk[i] || chk2[i+q] || chk3[i-q + n-1]) continue;
        chk[i] = 1;
        chk2[i+q] = 1;
        chk3[i-q + n-1] = 1;
        queen(q+1);
        chk[i] = 0;
        chk2[i+q] = 0;
        chk3[i-q + n-1] = 0;
    }
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    queen(0);
    cout << cnt;
}