[백준/C++]9663번_N-Queen

문제는 다음과 같습니다.

어려웠습니다. 저도 유튜브나 다른 자료를 참고해서 이 문제를 이해하고 해석하였으며 그 이후에 풀었습니다.
백트래킹의 정석과도 같은 문제인 것 같습니다.

저는 행을 기준으로, 퀸을 배치하였습니다.
row[k]=i;
이는 k행의 i번째 자리에 퀸을 배치하였음을 의미합니다.

해당 자리에 퀸을 배치하였다고 가정하고, 이 자리에 놓을 수 있다면
(➡️ 자리에 놓을 수 있는지에 대한 여부는 함수 check를 이용하였습니다.)

💡자리를 놓을 수 있는 지에 대한 여부

1. 같은 라인에 놓인 경우 -> row[i]==row[t]
2. 같은 대각선에 놓인 경우 -> abs(row[t]-row[i])==t-i
   (대각선의 경우, 좌표평면을 생각하면 쉽습니다.
   좌표평면에서 두 점의 "x 좌표 값의 차 = y 좌표 값의 차" 이면 같은 대각선에 놓입니다.)

NQueen 함수의 인자에 값을 +1 추가하여 그 다음 행에 대해서 수행합니다.

(2차원 배열으로는 시간초과가 나므로, 1차원 배열을 이용해야합니다.)

전체 코드는 다음과 같습니다.🙆🏻‍♀️

#include <bits/stdc++.h>
using namespace std;

int n, total=0;
int row[15];

bool check(int t){
    for(int i=0; i<t; i++){
        if(row[i]==row[t] || abs(row[t]-row[i])==t-i) return false;
    }
    // 같은 라인에 있거나 || 대각선에서 겹치는 경우 -> false 반환
    
    return true;
}

void NQueen(int k){
    if(k==n) total++;
    else{
        for(int i=0; i<n; i++){
            row[k]=i;
            if(check(k)) NQueen(k+1);
        }
    }
}

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

  cin>>n;
  NQueen(0);
  cout<<total<<"\n";
}

네 저는 이제 이거를 lisp로 짜야합니다...
프언 ... 이게 맞나요? 🤧