백준 9663번 : N-Queen [C#]

1. 모든 경우의 수를 다 체크하는 것 밖에 방법이 없을 것 같은데 윗줄부터 좌표로 접근해볼까?

> N*N 보드판에 퀸 N개를 놓으려면 같은 줄에 놓을 수 없으니까 모든 행과 열마다 퀸이 하나씩 들어가야겠다.

> 일단 이미 퀸이 있는 행엔 다른 퀸을 놓을 수 없으니 검사할 필요 없이 다음 행으로 넘어가자

> 순회하면서 이번 회차에 퀸을 저장한 좌표를 기억해둬야겠다. 그리고 순회의 끝에 도달했으면 퀸을 하나씩 빼서 다음 경우의 수가 있는지 확인해야겠다.

 

2. 루프를 돌면서 그 좌표에 놓을 수 있는지 확인하는 방법은?

> 행은 다르니까 열도 다른 퀸들과 다른지 확인하고, 대각선으로도 다른지 확인해야 한다.

> 열은 저장했던 퀸의 좌표와 비교한다.

 

3. 대각선이 같은 점들의 공통점이 뭘까?

>  왼쪽 위 > 오른쪽 아래로 긋는 대각선은 x-y값이 같고, 왼쪽 아래 > 오른쪽 위로 긋는 대각선은 x+y의 값이 같았다.

 

using System.Text;

class Program
{

    static int N;
    static int result = 0;
    static int[] pos; // pos[y] = x 에서 queen의 좌표는 x,y이다. 재귀를 y축을 기준으로 돌릴 거라
    // y행 x열에 queen을 놓았다는 뜻.

    static void Queen(int y)
    {
        if(y == N)
        {
            result ++;
            return;
        }

        for(int x=0; x<N; x++)
        {
            if(IsSafe(x, y))
            {
                pos[y] = x; // 퀸을 놓고
                Queen(y+1); // 다음 행으로 이동
                // isSafe 검사에서 현재 y값 이전까지만 검사하고 만약 값이 바뀐다면 
                // 덮어씌우기 때문에 상태 복구할 필요 없다.
            }
            
        }
    }

    static bool IsSafe(int x, int y)
    {
        // 같은 열인지 검사, 
        for(int i=0; i<y; i++)
        {
            if(pos[i] == x) return false; 
        }

        // 대각선에 해당하는지 검사
        for(int i=0; i<y; i++)
        {
            if(  (pos[i]- i) == (x-y) || (pos[i] + i) == (x+y) ) return false;
        }
        
        return true;
    }

    static void Main()
    {
        N = int.Parse(Console.ReadLine());

        pos = new int[N];

        Queen(0);

        Console.Write(result);
    }

}