[BOJ]9663-N-Queen

9663

#include <iostream>
#include <vector>

using namespace std;

int N;
int cnt=0;
vector<pair<int, int>> v;
vector<int> visited;

void dfs(int depth)
{
    if (depth == N)
    {
        cnt++;
        return;
    }

    for (int i = 0; i < N; i++)
    {
        bool check = true;
        for (int j = 0; j < depth; j++)
        {
            if (abs(i - visited[j]) != abs(depth - j) && visited[j] != i)
            {
                
            }
            else
            {
                check = false;
            }
        }

        if (check)
        {
            visited[depth] = i;
            dfs(depth + 1);
        }
    }

    return;
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        visited.push_back(-1);
    }

    dfs(0);

    cout << cnt;

    return 0;
}

처음에는 2차원 배열로 풀려고 했으나 시간이 너무 걸리고 답도 이상해서 바로 답을 찾아보았다.

1차원 배열로 짧은 코드로 푸는 방법이 있어 참고했다.

그럼에도 대각선에 있는지 탐색하는 부분에서 애를 먹었는데, 열과 행의 차이가 같을 때를 찾는 걸 보고 풀 수 있었다.

쉽지 않은 문제였따..

참고자료

---

9663 풀이