백트래킹 - KimTaebin-ai/study_posts GitHub Wiki

#include <stdio.h>

int N, M;
int arr[10];
int isUsed[10];

void func(int k) {
    if (k == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return ;
    }

    for (int i = 1; i <= N; i++) {
        if (!isUsed[i]) {
            arr[k] = i;
            isUsed[i] = 1;
            func(k + 1);
            isUsed[i] = 0;
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    func(0);
}

#include <stdio.h>

int isUsed1[40];
int isUsed2[40];
int isUsed3[40];

int cnt = 0;
int n;

void func(int cur) {
    if (cur == n) {
        cnt++;
        return;
    }

    for (int i = 0; i < n; i++) {
        if (isUsed1[i] || isUsed2[i + cur] || isUsed3[cur - i + n - 1])
            continue;
        isUsed1[i] = 1;
        isUsed2[i+cur] = 1;
        isUsed3[cur - i + n - 1] = 1;

        func(cur + 1);
        isUsed1[i] = 0;
        isUsed2[i+cur] = 0;
        isUsed3[cur - i + n - 1] = 0;
    }
}

int main() {
    scanf("%d", &n);
    func(0);
    printf("%d\n", cnt);
}