9663)N-Queen

문제

n*n의 체스 판 위에 n개의 퀸을 놓는 경우의 수를 구하는 문제
하나의 퀸이 놓인 가로, 세로 일직선 그리고 대각선에 다른 퀸이 놓일 수 없다.

풀이

(재귀함수 이용)
1. 퀸을 0번째 줄, 0번째 칸에 놓는다.
2. 첫번째 줄을 위한 queen함수를 호출한다. 해당 함수에서는 queen이 놓일 수 있는 자리를 구한다. 0번째 칸의 퀸이 놓인 자리, 0번째 칸의 퀸이 놓인 자리 ± 1(대각선)에는 놓일 수 없다.
3. 첫번째 퀸을 놓고 두번째 줄을 위한 queen함수를 호출한다.
4. 두번째 퀸이 놓일 수 있는 자리를 구한다. 첫번째 퀸때와 유사하다. 0,1번째 퀸이 놓인 자리와 그 대각선(1번째 퀸 ± (2-1), 0번째 퀸 ± (2-0))에는 놓일 수 없다.
5. 그렇게 n번째 퀸까지 놓일 수 있는 자리를 구하고, 놓일 수 있는 자리마다 다음 줄의 퀸을 위한 퀸 함수를 호출한다.

주의사항

처음 풀었을 때, 메모리 초과가 발생했다.
그 이유는 매번 pallet(퀸이 들어갈 수 있는 자리를 구하기 위한 n길이의 배열)을 만들고 delete하지 않았기 때문.
그리고 delete를 넣었더니 이번엔 틀렸다고 함.
그 이유는 이전에 만들었다가 delete한 pallet가 자동적으로 배정되었고, 초기화 되지 않은 채 이전 값들이 들어있었기 때문. 따라서 매번 new로 배열 생성 후 초기화를 해주어야 했다.

코드

//
//  9663.cpp
//  algorithm_study
//
//  Created by Jihyun Kyoung on 2023/08/01
//
#include<iostream>
using namespace std;
int sum=0;
void queen(int* arr, int h, int n);
int main(){
    int num;
    cin>>num;
    int *arr = new int[num];
    queen(arr, 0, num);
    cout<<sum<<endl;
}

void queen(int* arr, int h, int n){
    int* pallet= new int[n];
    for(int i=0;i<n;i++){
        pallet[i] = 0;
    }
    for(int i=0;i<h;i++){
        if(arr[i]+h-i<n)    
            pallet[arr[i]+h-i]=-1;
        if(arr[i]-(h-i)>-1)
            pallet[arr[i]-(h-i)]=-1;
        pallet [arr[i]] = -1;
    }
    if(h == n-1)
        for(int i=0;i<n;i++){
            if(pallet[i] != -1){
                sum +=1;
            }
        }

    else{
        for(int i=0;i<n;i++){
            if(pallet[i]!=-1){
                arr[h]=i;
                queen(arr, h+1, n);
            }            
        }
    }
    delete[] pallet;
}

힌트

https://www.youtube.com/watch?v=sUJkCXE4sAA