[BOJ 9663] N-Queen

🔗Link

문제
풀이

💡Idea

backtracking으로 퀸을 하나하나 놓아보면 된다. 같은 열과 행, 대각선들에 다른 퀸이 있는지 체크해줘야 한다. 대각선은 행과 열의 합과 차가 같은지로 체크할 수 있다.

• 대각선 \

i - j	1	2	3
1	1-1=0	1-2=-1	1-3=-2
2	2-1=1	2-2=0	2-3=-1
3	3-1=2	3-2=1	3-3=0

• 대각선 /

i + j	1	2	3
1	1+1=2	1+2=3	1-3=4
2	2+1=3	2+2=4	2+3=5
3	3+1=4	3+2=5	3+3=6

🔑Code

#include <bits/stdc++.h>
using namespace std;

int N, cnt = 0;
bool col[15];
bool diagDiff[29];
bool diagSum[29];

void func(int row){
    if(row == N){
        cnt++;
        return;
    }
    for(int i = 0; i < N; i++){
        if(col[i] || diagDiff[row - i + N - 1] || diagSum[row + i - (N - 1)]) continue;
        col[i] = true;
        diagDiff[row - i + N - 1] = true;
        diagSum[row + i - (N - 1)] = true;
        func(row+1);
        col[i] = false;
        diagDiff[row - i + N - 1] = false;
        diagSum[row + i - (N - 1)] = false;
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    func(0);
    cout << cnt;

    return 0;
}

🗨️ Side Notes

아자아자!