[백준] 9663번 : N-Queen (C++)

9663번 : N-Queen

---

문제)

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

 

 

출력 :

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 

 

 

 

 

풀이)

 

// 9663. N-Queen
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> vec;
 
int cnt = 0;
 
void recur(int cur)
{
    if (cur == n)
    {
        cnt++;
        return;
    }
    
    for (int i = 0; i < n; i++)
    {
        vec[cur] = i; 
        bool flag = false;
        for (int i = 0; i < cur; i++)
        {
            if (vec[cur] == vec[i] || cur - i == abs(vec[cur] - vec[i]))
            {
                flag = true;
                break;
            }
        }
 
        if (!flag)
        {
            recur(cur + 1);
        }
    }
}
 
 
int main()
{
    cin >> n;
    vec.resize(n + 1, 0);
 
    recur(0);
 
    cout << cnt;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/9663 

9663번: N-Queen