[Algorithm] Programmers :: N-Queen

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

프로그래머스

int queens[12] = { 0 };
int targetSize = 0;
int answer = 0;
 
bool check(int curY, int curX) // 윗행들의 퀸검사해서 놓을 수 있는지 
{
    for (int i = 0; i < curY; ++i) // 윗행들검사.
    {
        int prevY = i;
        int prevX = queens[i];
 
        if (prevX == curX) return false; // 같은 열에 있으니까
        if (prevY - prevX == curY - curX) return false;// 5시 
        if (prevY + prevX == curY + curX) return false;// 7시
    }
 
    return true;
}
 
 
void DFS(int y, int count)
{
    if (count == targetSize)
    {
        ++answer;
        return;
    }
 
    for (int i = 0; i < targetSize; ++i)
    {
        if (check(y, i)) // 놓을 수 있으면
        {
            queens[y] = i;
            DFS(y + 1, count + 1);
        }
    }
}
 
int solution(int n)
{
    targetSize = n;
 
    for (int i = 0; i < n; ++i)
    {
        queens[i] = -1;
    }
 
    for (int i = 0; i < n; ++i) // 열진행
    {
        queens[0] = i; // 0,i 에 퀸을 뒀다는 뜻.
        DFS(1, 1);
    }
 
    return answer;
}

복기겸 풀어본 문제.

대각선검사는 저렇게 따로 해도되고, 한번에 할 수 있는 방법도 있다.

if (abs(curRow - prevY) == abs(curCol - prevX)) return false;