[BaekJoon/백준] 9663번

N 퀸 문제다.

 

이전에 공부했던 8퀸문제의 변형문제이다.

 

8이 아닌, 입력받는 숫자로 동적으로 동작하게 끔 변경해준다.

#include <stdio.h>
#include <stdlib.h>

int *flag_a; // 각 행에 퀸을 배치했는지 체크하는 배열
int *flag_b; // 대각선 /에 퀸을 배치했는지 체크하는 배열
int *flag_c; // 대각선 \에 퀸을 배치했는지 체크하는 배열
int *pos; // 각 열에서 퀸의 위치
int n; // n x n
int cross_n; // 대각선 체크를 위한 배열 사이즈
int count = 0; // 경우의 수

// i 열에서 알맞은 위치에 퀸을 배치
void set(int i) {
    int j;
    for(j = 0; j < n; j++) {
        if(!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + n - 1]) {
            pos[j] = i;
            if(i == n - 1) // 배치 끝
                count++;
            else {
                flag_a[j] = flag_b[i + j] = flag_c[i - j + n - 1] = 1;
                set(i + 1);
                flag_a[j] = flag_b[i + j] = flag_c[i - j + n - 1] = 0;
            }
        }
    }
}

int main() {
    
    scanf("%d", &n);
    cross_n = n * 2 - 1; // ex) n=8일때, 최소는 0+0, 최대는 7+7. 따라서 8 * 2 - 1크기의 배열을 할당해주면 0~14까지의 숫자를 담아낼 수 있다.
    
    flag_a = calloc(n, sizeof(int));
    flag_b = calloc(cross_n, sizeof(int));
    flag_c = calloc(cross_n, sizeof(int));
    pos = calloc(n, sizeof(int));
    
    set(0);
    
    printf("%d\n", count);
    
    return 0;
}