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

[문제]

N개의 퀸이 서로 공격할 수 없게 만드는 경우의 수
[조건]

퀸은 <가로, 세로, 대각선> 으로 공격 가능하므로 그 경우를 제외한 조합을 찾아가면된다.
[해결방법]

백트레킹 활용

DFS를 활용해서 N개의 퀸이 서로 같은 라인이거나 대각선에 존재하지 않을 때를 찾아가면된다

https://mygumi.tistory.com/199

위 그림과같이 퀸이 놓일수 있는 1차원 배열 map[]이 존재할 때

현재의 map과 이전~현재까지의 map을 비교하여

같은라인인지 map[now] == map[yet]

대각선인지 map[now]-map[yet] == now-yet 판별해주면된다

[전체소스코드]

#define _CRT_SECUORE_NO_WARNINGS
#include <iostream>
#include <cmath>
#pragma warning(disable:4996)
using namespace std;

int map[15];
int test, result;
bool check(int line) {
    for (int i = 0; i < line; i++) {
        if (map[i] == map[line] ||				
            abs(map[line] - map[i]) == abs(line - i))
                return false;
    }
    return true;
}
void dfs(int cnt) {
    if (cnt == test) {
        result++;
        return;
    }
    for (int i = 0; i < test; i++) {
        map[cnt] = i;
        if (check(cnt)) dfs(cnt + 1);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> test;

    dfs(0);
    cout << result;
}