N-Queen 9663

문제

접근 방법

서로 공격할 수 없다는 것은 가로, 세로, 대각선으로 겹치지 않아야 한다는 것이다.
퀸을 놓을 때 기존에 퀸과 범위가 겹치는지 확인하면서 완전 탐색하면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> map; // 기존 y값
int N, ret = 0;
bool isOverlap(int i, int depth)
{
    for (int j = 0; j < depth; ++j) // 기존 x값
    {
        if (map[j] == i)
            return true;
        if ((j - map[j] == depth - i) || (j + map[j] == depth + i))
            return true;
    }
    return false;
}
void dfs(int depth) // 현재 x값
{
    if (depth == N)
    {
        ++ret;
        return;
    }
    for (int i = 0; i < N; ++i) // 새로운 y값
    {
        if (isOverlap(i, depth))
            continue;
        map[depth] = i;
        dfs(depth + 1);
        map[depth] = -1;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    map = vector<int>(N);
    dfs(0);
    cout << ret;
}

풀이

유명한 문제이지만 예전에 답을 본 적이 있어서 까먹을 때까지 기다렸다.
까먹지는 못했지만, 컨디션이 좋지 않은 지금 최적의 문제라고 생각하고 풀었는데 그때 해답이 어느 정도 기억에 남아서 어쩔 수 없이 내 완전한 힘으로 풀지 못했다.

배열을 가로 크기만큼만 만들어 주고 배열에는 세로의 값을 넣어준다.
만약 기존 배열에 같은 세로의 값이 존재한다면 세로로 겹친다는 뜻이다.
대각선을 확인하는 방법은 의외로 간단하다. 가로와 세로를 빼거나 더한 값이 같다면 같은 대각선이다. (왼쪽 대각선은 가로와 세로가 1씩 증가하고 오른쪽 대각선은 1씩 증감하기 때문이다)