백준 9663번: N-Queen / C++

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

 

접근 방법

다음부터는 문제를 완전히 이해하고 문제 풀이를 시작해야겠다. N개의 퀸이 아닌 내 마음대로 2개의 퀸일때 경우의 수를  생각했었다.......  다음으로 계속해서 아이디어에 대해서 고민을 많이 했지만 모든경우의 수를 탐색하느라 복잡했었는데 풀이를 확인하니 행한개에  한개의 퀸만 들어갈수 있다. 문제해결의 아이디어를 얻으니 풀이가 이해갔다. 그 이후에는 한칸씩 선택하고 이전  퀸위치와 비교해서 들어갈 수 있는 위치면 fasle 를 반환했다. 

---

 

#include <iostream>
 
using namespace std;
 
int N;
int Count = 0;
int Arr[15];
 
bool CheckCase(int col)
{
    for (int i = 0; i < col; ++i)
    {
        // 같은 열의 위치 or 기울기가 1 또는 -1
        if (Arr[i] == Arr[col] || i-col == Arr[i]-Arr[col] || col -i == Arr[i] - Arr[col])
            return true;
    }
    return false;
}
 
void DFS(int col)
{
    // 모든 행이 채워짐
    if (N == col)
    {
        ++Count;
        return;
    }
    // 다음 행을 찾는 과정
    for (int row = 0; row < N; ++row)
    {
        Arr[col] = row;
        if (CheckCase(col))
            continue;
        DFS(col + 1);
    }
 
}
 
int main()
{
    cin >> N;
 
    DFS(0);
    
    cout << Count;
 
    return 0;
}