[BOJ_C++] 9663번 : N-Queen

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int n, cnt = 0;
int list[15];

void N_Queen(int x) {
    bool flag;
    if (x == n)
        cnt++;
    else {
        for (int i = 0; i < n; i++) {
            list[x] = i;
            flag = true;
            for (int j = 0; j < x; j++) {
                if (list[x] == list[j] || abs(list[x] - list[j]) == (x - j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) N_Queen(x + 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    N_Queen(0);

    cout << cnt;
    return 0;
}

• 퀸은 오와 열을 따라 이동하는 것은 물론 대각선으로도 이동할 수 있다.
• 따라서 배열 list에 인덱스 값을 열(세로)로 고정한 뒤 해당 인덱스에 존재하는 값을 행의 위치(가로)로 취급하여 바꿔가며 퀸을 배치할 수 있는 곳을 찾을 것이다.
• N_Queen() 함수에서 x와 n이 같아진 경우는 겹치지 않는 경우에 수에 도달한 것이다. 따라서 cnt의 수를 1 증가시킨다.
• 아직 x과 n가 같아지지 않은 시점이라면 x열에 들어갈 수 있는 행의 값을 0에서 n 전까지 경우를 모두 실행하며 이전 열에 존재하는 행 값과 같지 않으며 대각선에 위치하지 않는 값이라면 다음 열을 호출한다.

결과