알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN

문제 링크 : 알고스팟 NQUEEN

문제 링크 : 백준 N-QUEEN

N-Queen문제, 즉 여왕말 문제는 백트래킹 관련으로 정말 유명한 문제이다. 백트래킹이란 그냥 다음 탐색을 진행하는데, 그 탐색이 유망하지 않으면 무시하고 돌아가서다시 탐색한다는 것(백트래킹,되추적) 이다.

출처 위키피디아

여왕말에서 유망한 탐색인지 아닌지를 검사하는 조건은 정말 간단하다. 그냥 지금까지 고른 말의 위치 중에서 같은 열에 속하는 게 있는지, 혹은 대각선에 위치하는 게 있는지 검사하고 있으면 이 탐색을 무시하고(가지치기하고) 되돌아가 다음 탐색을 진행(백트래킹)한다.

끝까지 도달하였으면, 가능한 경우를 찾은 것이므로 카운트를 증가 시키고 반환하여 다른 경우를 찾는다.

밑은 이 풀이에 해당하는 코드이다.

#include <cstdio>
#include <cmath>
int n, t, a[13], count=0;
//이 위치에 여왕 말을 놓을 수 있는지, 즉 유망한지 체크한다. 
bool check(int cur) {
    //0부터 이 행까지 모두 조사한다. 
    for (int i = 0; i<cur; i++) {
        //열이 같은 것이 있거나, 대각선 범위 내에 있으면 불가능한 경우므로 false을 리턴 
        if(a[i]==a[cur] || cur-i==std::abs(a[cur]-a[i])){
            return false;
        }    
    }
    return true;
}
void nqueen(int cur) { 
    //기저사례 : 끝에 도달하였으면 카운터를 증가 시키고 반환한다. 
    if(cur==n-1) {
        count++;
        return; 
    }
    //아직 끝에 도달하지 않았으면 다음 위치를 찾는다. 
    for(int i=0;i<n;i++){
        a[cur+1] = i;
        //이 위치가 유망한지 검사, check이 참이면 다음 여왕 말을 찾고, 못 찾으면 백트래킹한다.
        if(check(cur+1)){
            nqueen(cur+1);
        }
    } 
}
int main() {
    scanf("%d",&t);
    while(t--){
        count = 0;
        scanf("%d", &n);
        nqueen(-1);
        printf("\n%d\n",count);
    }   
}

근데 이렇게 가지치며 나가는 것보다 더 빠른 방법이 있는 것 같다. 좀 더 공부가 필요한듯하다..