[백준][C++] 9663: N-Queen

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

9663번: N-Queen

 

 

 

 

---

- 문제

 

  N * N 크기의 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수를 구하는 문제다.

 

 

---

- 해설

 

queen까지는 만들었는데, check을 할때 대각선을 어떻게 해야 할 지 생각을 못해서 check는 다른 사람꺼를 조금 참고했습니다.

 

y의 차이가 x의 차이랑 같으면 대각선이다 라는걸 생각 못해서 for문 두개 돌려서 찾고 있었네요. 

 

 

 

 

---

- 풀이

#include <iostream>
using namespace std;

int board[15] = {
    0,
};
int total = 0;

bool check(int cnt)
{
    for (int i = 0; i < cnt; i++)
    {
        if (board[i] == board[cnt] || abs(board[cnt] - board[i]) == cnt - i)
        {
            return false;
        }
    }
    return true;
}

void queen(int cnt, int N)
{
    if (cnt == N)
    {
        total++;
        return;
    }
    for (int i = 0; i < N; i++)
    {
        board[cnt] = i;
        if (check(cnt))
        {
            queen(cnt + 1, N);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, answer;
    cin >> N;
    queen(0, N);
    cout << total;
}

 

 

---

- 새롭게 알게 된 점