N-Queen

JM북과 함께 PS의 재미를 알게되고 삼주전? 부터인가 topcoder의 재미를 알게되었습니다.

지금까지는 그냥 단순한 알고리즘 이해 수준에 머물렀다면 앞으로는 PS를 많이 경험할 생각입니다.

topcoder를 재미를 알게된 3주전부터 C++를 하고 다른사람의 C++소스도 보고 있는데

C랑 비슷하면서도 많이 틀린...그런 오묘한 기분이네요.

 

C++공부하면서 STL도 써볼겸  NQUEEN 문제를 풀어봤습니다.

#include 
#include 
#include 
#include 

using namespace std;
#define MAX_N 12

struct Queen {
	int x, y;
};

set ch;

int solve(int row, int size,  vector& queen);

int main() {
	int T;
	int N;

	cin >> T;

	while(T--) {
		cin >> N;

		vector queen;
		cout << solve(0, N, queen) << endl;;
	}

	return 0;
}

bool check( vector& queen, int x, int y) {
	int t_x, t_y;
	if (ch.find(x) != ch.end()) return false;
	for (vector::iterator it = queen.begin();
		it != queen.end(); ++it) {
			t_x = it->x; t_y = it->y;
			if (t_x == x) return false;
			if (t_y == y) return false;
			if (abs(t_x - x) == abs(t_y - y)) return false;
	}
	return true;

}

int solve(int row, int size, vector& queen) {
	if (queen.size() == size) return 1;

	int ret = 0;

	for (int i = 0; i < size; ++i) {
		if (check(queen, i, row)) {
			struct Queen queen1;
			queen1.x = i; queen1.y = row;
			queen.push_back(queen1);
			ch.insert(i);
			ret += solve(row + 1, size, queen);
			ch.erase(i);
			queen.pop_back();
		}
	}
	return ret;
}

뭐 돌아가긴 가는데..........실행시간이........안습...ㅠ,ㅠ.

 

결국은 pan[MAX_N][MAX_N]으로해서 걸리나 안걸리나 check하면서 풀었다. ; )

아 재미져
제출하고 다른 사람소스 보니....흠....미친듯이 공부해야겠구나

void check(int x, int y, int size, int value) {
	int t_x, t_y;
	for (int i = 0; i < size; ++i) {
		pan[y][i] += value;
		pan[i][x] += value;
	}

	for(int i = x, j = y; i >=0 && j >=0; --i, --j) {
		t_x = i;
		t_y = j;
	}
	for (int i = t_x, j = t_y; i < size && j < size; ++i, ++j) 
		pan[j][i] += value;

	for(int i = x, j = y; i < size && j >= 0; ++i, --j) {
		t_x = i;
		t_y = j;
	}

	for (int i = t_x, j = t_y; i >= 0 && j < size; --i, ++j) 
		pan[j][i] += value;
}