#9663번 N-Queen (C++)

#include <iostream>
#include <cmath>
#define MAX 16
using namespace std;

int arr[MAX];
int N,ans = 0;

bool check(int num){
    for(int i=1; i<num; i++){
        if(arr[i]==arr[num]||num-i==abs(arr[num]-arr[i])) return false;
    }
    return true;
}

void dfs(int num){
    if(num==N) ans++;
    else{
        for(int i=1; i<=N; i++){
            arr[num+1] = i;
            if(check(num+1)==true) dfs(num+1);
            else arr[num+1] = 0;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    dfs(0);
    cout << ans << "\n";
    
    return 0;
}

백트래킹, 그 중에서 DFS의 개념을 이해하는데 큰 도움이 된 문제.

퇴근하고 4시간동안 정말 온갖 식을 짜서 고민해봤으며, 이때 도전했던 방식은

에라토스테네스의 체를 이용한 방식과 유사했다. (bool문으로 최대 15x15의 칸을 만드는 방식) 

보기좋게 틀렸고, 맞다가도 50% 넘어서는 오답이 됐고, 온갖 지저분한 수식을 달아서 겨우 완성했을 땐 시간 초과가 나왔다.

이게 정답이 아니겠다 싶어서 우선 남들의 방식을 봤고, 최대한 해설 없이 코드만 뚫어지게 본 다음

내가 이해한 범위에서 식을 세웠다.

 

재귀방식은 언제봐도 새롭다. 

하필이면 이 문제를 올린 주는 개인적으로 준비한 시험 준비, (큰)목적 성취에 이에 연이어 덮치는 허탈감, 방황이 휩쓴 기간이기 때문에 그다지 많은 공부를 하지 못했다.

 

새로운 기회고 주어졌고, 지식이 쌓이게 되었으니 하던 템포를 유지해서 꾸준히 나아가야겠다.