ABOUT ME

-

인기 태그


kafka elastic_search redis
Today
-
Yesterday
-
Total
-
  • N-Queen
    개발하면서/Algorithm,DS,PS 2013. 2. 2. 13:56

    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;
    }
    

    댓글 0

Designed by Tistory.