N-Queen

[문제 Link] https://programmers.co.kr/learn/courses/30/lessons/12952

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
n은 12이하의 자연수 입니다.

입출력 예

n	result
4	2

입출력 예 설명

로직

backtracking을 이용하여 모든 경우의 수를 다 구하면서 체스판에 n개의 퀸을 놓을 수 있는 경우만을 카운트하여 리턴한다.

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

class Solution
{
    public static int answer = 0,n = 0;
    public static bool[] col = new bool[16];
    public static bool[] inc = new bool[31];
    public static bool[] dec = new bool[31];
    public static int solution(int nn) {
        n = nn;
        queen(1);
        return answer;
    }
    public static void queen(int r)
    {
        if (r > n)
        {
            answer++;
            return;
        }

        for (int i = 1; i <= n; i++)
        {
            if (!col[i] && !inc[r + i] && !dec[n + (r - i) + 1])
            {
                col[i] = inc[r + i] = dec[n + (r - i) + 1] = true;
                queen(r + 1);
                col[i] = inc[r + i] = dec[n + (r - i) + 1] = false;
            }
        }
    }
    
    public static void Main(string[] args)
    {
        Console.Write(solution(4));
    }
}

N-Queen [프로그래머스](C#)