LC52. N-Queens II

작성일

문제: https://leetcode.com/problems/n-queens-ii/

  • 손쉽게 풀 수 있는 Bruteforce 문제.
  • 공간 복잡도를 N으로 만들수 있는게 포인트
  • 처음에는 구조체로 풀었는데, 이후 비트마스크를 쓰니까 겁나 빨라짐.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
	struct cell {
		bool left, down, right;
	};
	
	int go(vector<cell>& prev, int cur, int n) {
		if(cur == n) return 1;
		vector<cell> row(n);
		for(int i = 0; i < n; i++) {
			if(i >= 1 && prev[i].left) row[i-1].left = true;
			if(prev[i].down) row[i].down = true;
			if(i < n-1 && prev[i].right) row[i+1].right = true;
		}
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			if(!row[i].left && !row[i].down && !row[i].right) {
				row[i] = {1,1,1};
				cnt += go(row, cur+1, n);
				row[i] = {0,0,0};
			}
		}
		return cnt;
	}

    int totalNQueens(int n) {
        vector<cell> row(n);
		return go(row, 0, n);
    }
};