[알고리즘 문제 풀기] N-Queen(9663)

1. 문제 풀이 아이디어

• 체스판에 퀸을 배치할 때 같은 행, 대각선 방향을 체크하여 백트래킹으로 가능한 경우의 수를 구해 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    bool[] chky = new bool[n];
    bool[] chkinc = new bool[n * 2];
    bool[] chkdec = new bool[n * 2];
    int result = 0;
    for (int i = 0; i < n / 2; i++)
    {
        chky[i] = true;
        chkinc[i + n] = true;
        chkdec[i] = true;
        Solve(1);
        chky[i] = false;
        chkinc[i + n] = false;
        chkdec[i] = false;
    }
    result *= 2;
    if (n % 2 == 1)
    {
        chky[n / 2] = true;
        chkinc[n / 2 + n] = true;
        chkdec[n / 2] = true;
        Solve(1);
    }
    sw.WriteLine(result);
    void Solve(int x)
    {
        if (x == n)
        {
            result++;
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (chky[i]) continue;
            if (chkinc[i - x + n]) continue;
            if (chkdec[i + x]) continue;
            chky[i] = true;
            chkinc[i - x + n] = true;
            chkdec[i + x] = true;
            Solve(x + 1);
            chky[i] = false;
            chkinc[i - x + n] = false;
            chkdec[i + x] = false;
        }
    }
}

3. 정리

• chky[i] 배열로 같은 열에 퀸이 있는지 확인한다.

• chkinc[i - x + n] 배열로 증가하는 대각선(↗)에 퀸이 있는지 확인한다.

• chkdec[i + x] 배열로 감소하는 대각선(↘)에 퀸이 있는지 확인한다.

• 절반만 탐색하고 결과를 두 배로 곱하여 연산을 줄인다.

• n이 홀수일 때 중앙 행의 경우를 따로 계산하여 중복을 방지한다.