N-Queens

못풀었음.

https://programmers.co.kr/learn/courses/30/lessons/12952

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int col[13] = { 0, };
int LoopSize(0);
int answer(0);

bool chk(int Depth)
{
    for (int i = 0; i < Depth; i++)
    {
        if ((abs(Depth - i) - abs(col[Depth] - col[i]) == 0) || (col[Depth] == col[i]))//대각선분 또는
        {
            return false;
        }
    }
    return true;
}

void dfs(int Depth)
{
    if (Depth == LoopSize)
    {
        answer++;
        return;
    }

    for (int i = 0; i < LoopSize; i++)
    {
        col[Depth] = i;

        if (true == chk(Depth))
        {
            dfs(Depth + 1);
            col[Depth] = 0;
        }
    }
}


int solution(int n) {
 
    LoopSize = n;


    dfs(0);

    return answer;
}

[백트래킹 정리]
완전탐색을 기본으로 하는데,DP와는 구조적으로 다름

처음 시작도

for (int i = 0; i < arr_size; i++)
	{
		Col[col] = i;//한 열에 해당되는곳 모두 탐색
		if (check(Col[col]))
		{
			backtracking(col + 1);//다음 열 투입한다.
		}
	}

포문 기반으로 그림에서 펼쳐지는것처럼 백트래킹 하고(재귀)
그 함수 내부에서 뻗쳐갈 조건이 아니면 바로 return false한다.
이를통해 사진에서 X자 표시하는 내용들이 생겨지는 것이다.