BaekJoon 9663 N-Queens

Link : https://www.acmicpc.net/problem/9663

소스 결과 : 1988 KB / 4588 ms 성공

출처 : BackJoon

 

설명

백준 Back Tracking 기초 문제

Back Tracking 대표 문제라고해서 풀어봤는데 이틀이나 걸렸다.

 

알고리즘을 2번 고쳤는데

처음에는 15 by 15 배열을 만들어 기록 하는 방식으로 제작했다가

타임아웃의 늪에 빠졌다.

같은 열을 제외하는 부분을 없애고 대각선 계산도 개선 해봤지만 결과는 똑같이 타임아웃

 

성공한 알고리즘은 2차원 행렬을 만드는게 아닌

현재 저장된 지점들을 스택처럼 저장하는 15 by 2 배열을 만들어 저장하고

현재 저장된 배열들을 재 탐색 하면서 사용 가능한 곳인지 확인하는 방법

 

구글링을 해보고 느낀거지만 훨씬 빠른 방법도 존재..

타임아웃이 조금더 빡빡하다면 실패했을지도..

 

소스코드

#include <iostream>

using namespace std;

int res = 0;

bool isAble(int x, int y, int line, const int point[15][2])
{
	for (int j = 0; j < line + 1; j++) // current Line
		if (point[j][0] == x || abs(point[j][0] - x) == abs(point[j][1] - y))
			return false;

	return true;
}

void algorithm(int x, int y, int n, int point[15][2])
{
	if (y + 1 == n)
	{
		res++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (isAble(i, y + 1, y, point))
		{
			point[y + 1][0] = i; point[y + 1][1] = y + 1;
			algorithm(i, y + 1, n, point);
		}
	}
}

int main()
{
	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int point[15][2];

		point[0][0] = i;
		point[0][1] = 0;

		algorithm(i, 0, n, point);
	}

	cout << res;

	return 0;
}