(프로그래머스 c++) N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

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

 

DFS로 문제 풀이.

퀸이 움직이는 방향을 모두 검사하면서 카운트를 세어주면 된다.

상하좌우, 대각선을 모두 검사하는 함수를 만들어서 dfs를 진행하면 된다.

#include <string>
#include <vector>

using namespace std;
bool check[12][12] = {false, };
int answer = 0;

void dfs(int n, int row, int column, int queen);
bool isTrue(int n, int row, int column);

int solution(int n) {
    dfs(n, 0, 0, 0);
    
    return answer;
}

void dfs(int n, int row, int column, int queen)
{
    if(queen == n)
    {
        answer++;
        return;
    }
    
    for(int j = 0; j < n; j++)
    {
        if(isTrue(n, row, j))
        {
            check[row][j] = true;
            dfs(n, row + 1, j, queen + 1);
            check[row][j] = false;
        }
    }
}

bool isTrue(int n, int row, int column)
{
    //가로
    for(int i = 0; i < n; i++)
    {
        if(check[row][i] == true)
            return false;
    }
    
    //세로
    for(int i = 0; i < n; i++)
    {
        if(check[i][column] == true)
            return false;
    }
    
    //우측 상방 대각
    for(int i = row, j = column; i >= 0 && j < n; i--, j++)
    {
        if(check[i][j] == true)
            return false;
    }
    
    //우측 하방 대각
    for(int i = row, j = column; i < n && j < n; i++, j++)
    {
        if(check[i][j] == true)
            return false;
    }
    
    //좌측 상방 대각
    for(int i = row, j = column; i >= 0 && j >= 0; i--, j--)
    {
        if(check[i][j] == true)
            return false;
    }
    
    //좌측 하방 대각
    for(int i = row, j = column; i < n && j >= 0; i++, j--)
    {
        if(check[i][j] == true)
            return false;
    }
    return true;
}