코영방

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

N-Queen문제 생각보다 어렵죠? 아마도 N-Queen문제에서 막혀서 찾아오셨다면, 아마도 백트랙킹 / 재귀함수에 대해서 아주 조금 이해가 힘드셔서 오셨을것 같네요.^^ 아래 코드보시면서 도움 되시기 바랍니다.

각 행을 한개씩 내려가면서 Queen을 놓을 곳을 찾아가면 될것 같다.

첫번째 행의 어느 열에 Queen을 위치시키면, 그 열과 대각선 방향을 더이상 Queen을 놓을수 없음을 표시해야 한다.

bool check_right_up[100]; //이미 대각선 오른쪽 위로 queen이 있는지 확인
위 코드는 아래 그림을 보고 이해할 수 있길 바랍니다. 대각선의 각 cell의 행값 + 열값은 unique하다는 걸 이용해서,

그 unique한 값을 배열의 index로 사용해서, 그 대각선에 이미 Queen이 위치해 있음을 판단하면 됩니다.

bool check_right_down[100]; //이미 대각선 오른쪽 아래로 queen이 있는지 확인

아래 그림은 행-열을 한 값을 표시하고 있다. 음수가 발생하니, 모든 값들에 N을 더하면,

1,2,3,4,5,6,7 로 unique한 값을 만들수 있고, 이것을 배열의 index로 이용하면 됩니다.

#include <bits/stdc++.h>
using namespace std;
bool a[15][15];
int n;
bool check_col[15]; //이미 그 열에 queen이 있는지 확인
bool check_right_up[100]; //이미 대각선 오른쪽 위로 queen이 있는지 확인
bool check_right_down[100]; //이미 대각선 오른쪽 아래로 queen이 있는지 확인

void check_onoff(int row, int col, bool onoff)
{
    check_right_up[row + col] = onoff;
    check_right_down[row - col + n] = onoff;
    check_col[col] = onoff;
    a[row][col] = onoff;
}
bool check(int row, int col) {
    // 같은 열 확인
    if (check_col[col]) {
        return false;
    }
    // 오른쪽 위방향 대각선 확인 (왼쪽 아래도^^)
    if (check_right_up[row + col]) {
        return false;
    }
    // 오른쪽 아래 방향 대각선 확인 (왼쪽 위도^^)
    if (check_right_down[row - col + n]) {
        return false;
    }
    return true;
}

int N_Queen(int row) {
    if (row == n) {
        return 1;
    }
    int cnt = 0;
    for (int col = 0; col < n; col++) {
        if (check(row, col)) { //이 row, col위치에 놓을수 있을지 확인
            check_onoff(row, col, true);  //놓을 수 있으니까, 그 위치 관련해서 놓았다는 표시를 함
            cnt += N_Queen(row + 1);  //다음 행에 queen을 놓으로 감.
            check_onoff(row, col, false); //row, col 기준으로 확인해보 후 임으로, 다시 해제함.
        }
    }
    return cnt;
}
int main() {
    cin >> n;
    cout << N_Queen(0) << '\n';
    return 0;
}