[백준/C++] 9663번 N-Queen

백준

 

---

🤔문제 이해

퀸은 자신이 위치한 행과 열, 그리고 양쪽 대각선을 다 공격할 수 있으므로 퀸이 공격할 수 없는 공간에 또 다른 퀸을 놓으며 N개의 퀸을 모두 놓는 방법의 수를 구하는 문제이다. 체스를 몰라서 따로 검색해보고 문제를 이해할 수 있었다.(문제가 불친절..)

---

🔥풀이🔥

한 행에서 퀸을 둘 수 있는 열에 퀸을 놓아보고 그 때의 공격범위를 업데이트해줬다가 리턴하면 공격범위를 그 전으로 초기화해주고 해당 행에서 다음 가능한 열에 두는 경우로 넘어간다.

 

변수

- length : 퀸이 공격할 수 있는 열의 위치를 비트마스크로 표현

- diag1 : 퀸이 공격할 수 있는 오른쪽위방향 대각선을 비트마스크로 표현

- diag2 : 퀸이 공격할 수 있는 왼쪽위방향 대각선을 비트마스크로 표현

 

재귀함수 void Solve(int i, int cnt) 

- 현재 상태 : 퀸을 놓을 i번째 행과 놓여진 퀸의 갯수 cnt

- 다음 상태 : 다음 행

- 진입 상태 : 0번째 행, 0개의 퀸

- 종료 상태 : 퀸이 n개 놓였을 때 return 

- 퀸이 놓이면 공격 범위를 나타내는 length, diag1, diag2의 값을 업데이트

 

함수 vector<int> AvailableNum() 

- 현재 행에서 퀸을 둘 수 있는 열의 좌표를 담은 벡터를 return

 

✍️ 후기

한 행에는 무조건 하나만 둘 수 있으니 그 행에 퀸을 하나두면 바로 다음 행으로 넘어가야 했다..! 보드의 모든 칸을 다 돌게 되니 시간초과가 날 수 밖에 ㅠ

---

#include <iostream>
#include <vector>

using namespace std;

int n;
int length, diag1, diag2;
int ans;

bool isValid(int i, int j) {
    if ((diag1 & (1 << (i + j))) != 0) return false;
    if (i - j > 0) {
        i = i - j;
        j = 0;
    } else {
        j = j - i;
        i = 0;
    }

    if (i == 0) {
        if ((diag2 & (1 << (j + n))) != 0) return false;
    } else if (j == 0) {
        if ((diag2 & (1 << i)) != 0) return false;
    }
    return true;
}

vector<int> AvailableNum() {
    vector<int> tmp;
    for (int j = 0; j < n; j++) {
        if ((length & (1 << j)) == 0)
            tmp.push_back(j);
    }
    return tmp;
}

void Solve(int i, int cnt) {
    if (cnt == n) {
        ans++;
        return;
    }
    if (i == n) return;
    int tmp_length = length;
    int tmp_diag1 = diag1;
    int tmp_diag2 = diag2;

    vector<int> x = AvailableNum();
    for (int j: x) {
        if (isValid(i, j)) {
            length = length | (1 << j);
            diag1 = diag1 | (1 << (i + j));
            int ni = i;
            int nj = j;
            if (ni - nj > 0) {
                ni = ni - nj;
                nj = 0;
            } else {
                nj = nj - ni;
                ni = 0;
            }
            if (ni == 0)
                diag2 = diag2 | (1 << (nj + n));
            else
                diag2 = diag2 | (1 << ni);

            Solve(i + 1, cnt + 1);

            length = tmp_length;
            diag1 = tmp_diag1;
            diag2 = tmp_diag2;
        }
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n;
    Solve(0, 0);
    cout << ans;
}