백준 9663번, N-Quuen(C, C++)

        #include<iostream>

        using namespace std;
        int N;
        int solution = 0;
        int row[15];

        bool check(int level){
            for(int i = 0; i < level; i++){
                if(row[i] == row[level] || abs(row[level] - row[i]) == (level - i)){
                    return false;
                }
            }
            return true;
        }
        void nqueen(int cnt){
            if(cnt == N){
                solution++;
            }else{
                for(int i = 0; i < N; i++){
                    row[cnt] = i;
                    if(check(cnt)){
                        nqueen(cnt + 1);
                    }
                }
            }
        }

        int main(){
            cin>>N;
            nqueen(0);
            cout<<solution;
            return 0;
        }

백트레킹에 관한 대표적인 문제입니다.

 

열에 대한 값을 넣으면 행이 나오도록 배열을 만들어줍니다.

하나의 열에 0부터 N-1까지의 행까지 퀸이 들어가는 경우를 for문과 재귀함수를 이용하여 구현합니다.

퀸이 서로 있으려면, 대각선의 경우와 같은 줄이 있으면 안되는 규칙이 있기 때문에

체크 함수를 만들어 return값이 true나 false가 나오도록합니다.

규칙에 부합하는 경우 cnt + 1을 시켜 다음 열을 확인합니다.

만약 부합하지 않는 경우, 그 해당 열에 대한 행을 반복문의 증가로 인해 다음의 행을 확인합니다.