아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.

• 틀린거 없음!

N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

입출력 예

풀이

#include <string>
#include <vector>
#include <iostream>
#include <array>
using namespace std;
void point_check(vector<vector<int>> &table, int n, int col, int row, int value)
{
    int i =0;
    for(; col < n; col++)
    {
        table[row][col] += value;
        if(row - i >= 0)
            table[row - i][col] += value;
        if(row + i < n)
            table[row + i][col] += value;
        i++;
    }
}

void dfs(vector<vector<int>> &table, int n, int col, int row, int &answer)
{
    if (n == col)
    {
        answer++;
        return;
    }
    for(row = 0; row < n; row++)
    {
        if(table[row][col] == 0)
        {
            point_check(table,n,col,row,1);
            dfs(table, n, col + 1, row, answer);
            point_check(table,n,col,row,-1);
        }
    }
}

int solution(int n) {
    int answer = 0;
    vector<vector<int>> table(n,vector<int>(n,0));
    dfs(table, n, 0, 0, answer);  
    return answer;
}

설명

• q를 놓을 수 있는 위치를 정해 판별해야한다.
• 왼쪽 부터 q를 놓아보고, q를 놓은 자리에서 오른쪽 대각선 직선 들에 못놓는다고 기록을 남겨두었다.
• dfs의 for에서 같은 열에 행을 바꿔가며, 퀸을 놓아본다.
• 만약 해당 row, col자리의 값이 0이라면 놓아도 되는 자리이므로,
• 해당 자리에 q을 놓는데, 그 자리에 놓게되면 다음 퀸을 놓을때 못놓는 자리가 생기므로, 못놓는다는걸 배열에 표시해주고, col+1을 해주어 다음 열의 q은 어느 위치에 놓을지 선택해주게 로직을 구상하였다.