Algorithm :: N Queen

* 정보 올림피아드 1889번 문제입니다.

 시간초과 때문에 시간 줄여볼거라고 삽질하다보니 매크로 함수들을 만들었네요.

 풀이 방법은 백트래킹을 썼고, 백트래킹만 쓰니 입력값이 13일 때 시간초과가 떴었습니다. 시간초과는 N / 2만큼만 루프돌아서 나온 경우의 수를 2배시켜 해결했습니다. N이 홀수인 경우는 중간값으로 한번더 순회한 결과로 나온 경우의 수를 더해줬습니다.

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

#define MAX_N 14

typedef struct _stack
{
	int top;
	int data[MAX_N];
} stack;

int N, result;
stack queens;

#define push(x) queens.data[queens.top++] = x
#define pop() queens.data[--queens.top]
#define peek() queens.data[queens.top - 1]
#define my_abs(x) ( (x) & 0x80000000 ? (~(x) + 1) : (x) )

void backtracking()
{
	if(queens.top^N)
	{
		register int x, i, ok;
		for(x = 1 ; x <= N ; x++)
		{
			ok = 1;
			for(i = 0 ; i < queens.top ; i++)
			{
				if(!(queens.data[i]^x) ||
					!(my_abs(queens.data[i] - x)^my_abs(i - queens.top)))
				{
					ok = 0;
					break;
				}
			}
			if(ok)
			{
				push(x);
				backtracking();
			}
		}
	}
	else
	{
		result++;
	}
	pop();
}

int main()
{
	FILE *fin = fopen("input.txt", "r"), *fout = fopen("output.txt", "w");
	int x;

	fscanf(fin, "%d", &N);

	for(x = 1 ; x <= (N >> 1) ; x++)
	{
		push(x);
		backtracking();
	}
	result *= 2;
	if(N & 1)
	{
		push((N >> 1) + 1);
		backtracking();
	}

	fprintf(fout, "%d", result);

	fclose(fin);
	fclose(fout);

	return 0;
}