[BackTracking] NQueen

문제 출처 : http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1889

나의 답 : 아래 코드이다.. 하지만 N = 13일경우 1초내에 계산이 안되서 accepted되었다..ㅠㅠ 속도 향상할 수 있는 point를 찾아야 겠다..

#include 
#include 
#define DEBUG 0
#define MAX_QUEENS 14

int g_cols[MAX_QUEENS]; // represent of chess board
                        // g_cols[index] : column, index : row
int g_num_queens;
int g_num_possible_sequence;

void SetInputFromFile(const char* fileName);
void PrintAnswerToFile(const char* fileName);
void NQueen(int irow);
int isThreathen(int irow);
void Print_Queen();

int main() {

    SetInputFromFile("input.txt");
    g_num_possible_sequence = 0;
    NQueen(0);
    PrintAnswerToFile("output.txt");

    return 0;
}

void SetInputFromFile(const char* fileName) {
    FILE *input = fopen(fileName, "r");
    if (input == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    //TODO:
    fscanf(input, "%d", &g_num_queens);
    fclose(input);
    return;
bail:
    if (input != NULL) fclose(input);
}

void PrintAnswerToFile(const char* fileName) {
    FILE *output = fopen(fileName, "w");
    if (output == NULL) {
        fprintf(stderr, "Can NOT open file: \n", fileName);
        goto bail;
    }

    //TODO:
    fprintf(output, "%d\n", g_num_possible_sequence);
    fclose(output);
    return;
bail:
    if (output != NULL) fclose(output);
}

void NQueen(int irow) {
    int icol;
    if (DEBUG) {printf("nqueen(%d)\n", irow + 1); Print_Queen();}
    if (isThreathen(irow)) {
        if (DEBUG) {printf("irow(%d) is Threathen\n", irow);Print_Queen();}
        return;
    }
    if (irow == g_num_queens) {
        if (DEBUG) {printf("completed\n");Print_Queen();}
        g_num_possible_sequence++;
        return;
    }

    for (icol = 1; icol <= g_num_queens; icol++) {
        g_cols[irow + 1] = icol;
        NQueen(irow + 1);
    }
}

int isThreathen(int irow) {
    int k; // irow 보다 작은 row를 가리키는 index
           // TODO : rename k

    for (k = 1; k < irow; k++) {
        if (g_cols[irow] == g_cols[k]
            || abs(g_cols[irow] - g_cols[k]) == (irow - k)) {
            return 1;
        }
    }

    return 0;
}

void Print_Queen() {
    int i;
    for (i = 1; i <= g_num_queens; i++) {
        printf("%d ", g_cols[i]);
    }
    printf("\n");
}