9663 - N-Queen

9663 문제 링크

접근법

Backtracking을 통해 유망성을 검사한다. dfs함수에서 N_line == N+1 이면 마지막 줄까지 확인이 다 된거이므로 gcase를 ++시킨다. x는 1~N까지 검사하며 Queen_check를 통해 Queen이 놓여 질 수 있는 자리인지를 확인하고 놓을 수 있다면 다음줄로 넘어간다. x 좌표가 같거나 놓으려는 위치의 x좌표와 놓여져 있는 Queen의 x좌표의 차 가 각각의 y좌표의 차와 같다면 대각선 이라는 의미고 이때 또한 Queen을 놓을 수 없다.

#include <iostream>
#include <cstdlib>

using namespace std;
int N;
int gcase;
int Line[15] = {0,};

bool Queen_check(int y)
{
    for(int i=1; i<y; i++)  
    {

        if(Line[i] == Line[y])
        {
            return false;
        }

        if(abs(Line[i] - Line[y]) == abs(i - y))
        {
            return false;
        }
    }
    return true;
}

void dfs(int N_line)
{
    if(N_line == N+1)
    {
        gcase++;
    }
    else
    {
        for(int x=1; x<N+1 ;x++)
        {
            Line[N_line] = x;
            if(Queen_check(N_line))
            {
                dfs(N_line + 1);

            }
            else
            {
                Line[N_line] = 0;
            }


        }

    }
}

int main(int argc, char *argv[])
{
    scanf("%d", &N);

    for(int i=1; i<N+1; i++)
    {
        Line[1] = i;
        dfs(2);
    }

    cout <<gcase;
    return 0;
}

결론

Backtraking과 재귀함수를 사용하면서 꽤 어려웠던것 같다. 역시 공부가 더 필요할 거 같다.