[C/C++] BOJ 9663 :: N-Queen

BOJ 9663 :: N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663

나의 풀이

1. backtracking 방법으로 queen을 놓으며 방법의 개수를 센다.

2. 반환조건 : 1. N개의 queen을 모두 놓은 경우 ans를 갱신하고 return.

  2. 현재 행에 queen을 놓지 못하고 다음 행으로 넘어간 경우 return. (col >= N)

  (N*N 행렬에 N개의 queen을 놓으려면 한 행에 하나의 queen이 반드시 놓여져야만 한다.)

  3. 탐색 행이 N을 넘어간 경우 return. (row >= N)

  (마지막 행까지 queen을 놓았는데 N개의 queen을 놓지 못한 경우)

3. ▥, ▤, ▨, ▧ 방향에 queen이 채워져 있지 않은 경우,

queen을 놓고 다음 행의 첫번 째 열을 탐색한다.

4. queen을 놓지 않고 다음 열을 탐색한다.

▨, ▧ 방향에 queen이 놓여져 있는지 확인하는 배열을 아래 코드로 작성한 이유는

여기 확인 => [C/C++] BOJ 1799 :: 비숍

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_9663/BOJ_9663.cpp

// 백준알고리즘 9663번 :: N-Queen
#include<iostream>
using namespace std;
 
int N;
int l[30], r[30], u[15], d[15];
int ans = 0;
 
// 놓을 수 있는 N-Queen의 방법의 수를 구하는 함수
void tracking(int row, int col, int count)
{
    // N개의 queen을 놓았다.
    if (count == N)
    {
        ans++;
        return;
    }
    // 한 행에 queen이 놓여져있지 않거나 체스판의 범위를 넘어갔으면 return
    if (col >= N || row >= N)
        return;
 
    if (!l[col - row + N - 1] && !r[row + col] && !u[col] && !d[row])
    {
        l[col - row + N - 1] = r[row + col] = u[col] = d[row] = 1;
        tracking(row+1, 0, count + 1);
        l[col - row + N - 1] = r[row + col] = u[col] = d[row] = 0;
    }
    tracking(row, col+1, count);
}
 
int main(void)
{
    cin >> N;
    tracking(0, 0, 0);
    cout << ans;
 
    return 0;
}