[알고리즘/C#] 프로그래머스 - N-Queen

✏️ 풀이 방법
예전에 백준에서 풀었던 문제다.
서로를 공격할수 없게하려면 기본적으로 같은 행, 같은 열에는 배치할 수 없다.
따라서 첫번째 행부터 열마다 하나씩 배치해보면 된다.
같은 열이 아니고, 대각선으로도 닿지 않는 위치에 배치한다.

using System;
using System.Collections.Generic;

public class Solution {
    int N;
    List<int> cols;

    private bool CheckPos(int row)
    {
        for (int i = 0; i < row; ++i)
        {
            if (cols[row] == cols[i])
                return false;

            if ((row - i) == Math.Abs(cols[row] - cols[i]))
                return false;
        }

        return true;
    }

    private void SetQueen(int row, ref int answer)
    {
        if (row == N)
        {
            answer++;
            return;
        }
        else
        {
            for (int i = 0; i < N; ++i)
            {
                cols[row] = i;

                if (CheckPos(row))
                {
                    SetQueen(row + 1, ref answer);
                }
            }
        }
    }

    public int solution(int n)
    {
        int answer = 0;
        N = n;

        cols = new List<int>();
        for (int i = 0; i < n; ++i) cols.Add(0);

        SetQueen(0, ref answer);

        return answer;
    }
}