N - Queen

문제

문제 풀이

using System;

public class Solution
{
    // N개의 퀸을 배치할 수 있는 방법의 수
    private int answer = 0;
    private bool[] col;
    private bool[] diag1;
    private bool[] diag2;

    // 퀸을 배치하는 메서드
    public int solution(int n)
    {
        col = new bool[n];
        diag1 = new bool[2 * n - 1];
        diag2 = new bool[2 * n - 1];

        // 첫 번째 행부터 시작하여 백트래킹
        Backtrack(0, n);

        return answer;
    }

    // 백트래킹을 이용하여 퀸을 배치하는 함수
    private void Backtrack(int row, int n)
    {
        if (row == n)  // 퀸이 N개 배치되었으면 경우의 수를 증가
        {
            answer++;
            return;
        }

        for (int c = 0; c < n; c++)
        {
            // 열, 대각선에 이미 퀸이 존재하면 그 자리는 배치할 수 없다
            if (col[c] || diag1[row + c] || diag2[row - c + n - 1])
                continue;

            // 퀸을 배치할 수 있으면 해당 자리를 차지
            col[c] = true;
            diag1[row + c] = true;
            diag2[row - c + n - 1] = true;

            // 다음 행으로 퀸을 배치
            Backtrack(row + 1, n);

            // 배치한 퀸을 제거하고, 다음 자리를 시도
            col[c] = false;
            diag1[row + c] = false;
            diag2[row - c + n - 1] = false;
        }
    }
}