[BOJ] 9663 - N-Queen (C++)

문제

N-Queen

코드

#include <iostream>

using namespace std;

int col[15];
int N, total = 0;

bool check(int level){
    for(int i = 0; i < level; i++)
        if(col[i] == col[level] or abs(col[level] - col[i]) == level - i)
            return false;
    return true;
}

void nqueen(int x){
    if(x == N) total++;
    else {
        for(int i = 0; i < N; i++){
            col[x] = i; 
            if(check(x)) nqueen(x+1);
        }
    }
}

int main() {
    cin >> N;
    nqueen(0);
    cout << total;
}

접근

퀸을 놓는 문제는 잘 알려져 있는 것에 비해 처음 풀어보았다. 먼저 든 생각은 먼저 놓은 퀸을 조건에 맞게 놓을 수 있다면 마지막으로 퀸을 두었을 때 그 방법의 수들을 증가시키면 되지 않을까 였다. 이를 위해 해당 열에 위치한 퀸의 행을 표시하는 1차원 배열을 사용하였다.

col[x] = y // x열에 놓인 퀸의 행은 y -> (y,x)

이제 퀸을 놓을 때 상하좌우, 대각에 다른 퀸이 있는지 확인하는 과정이 남았다. 상하좌우의 경우 열은 매번 달라지기 때문에 논외가 되었고 좌우의 경우 이제껏 위치한 퀸들이 같은 행에 있는지 확인해주면 되었다. 문제는 대각이었다. 이는 x, y 좌표의 차이를 가지고 비교하였다. 이 값이 같다면 두 점은 대각에 위치하게 된다.

(1,3) 을 기준으로 (2,4)은 대각에 위치하지만 (1,5)는 대각에 위치하지 않는다.