프로그래머스 Lv2 N-Queen

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

프로그래머스

나는 이 문제를 DFS로 풀었다. 

퀸을 배치하는 배열을 선언하고, DFS 호출 시 퀸을 ROW에 배치 할 때 마다 모든 COLUMN에 퀸을 배치시키면서  

퀸이 배치가 가능한지 검사하는 함수를 만들어 문제를 풀었다. 

세로 가로 부분을 검사하는 부분이 생각보다 단순 했는데, 나는 퀸의 좌우를 검사하는 것을 0 - N까지 검사하면 더 쉬웠다.

#include <string>
#include <vector>

using namespace std;

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

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

void dfs(int n, int row, int column, int queen)
{
    if(n == queen)
    {
        ++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;
        }
    }
}

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