9663 N-Queen

이전에 풀었을 때 코드를 보니 이차원배열을 다 확인해서 시간이 일차원배열로 풀었을 때보다 두배나 더들었다.

1년전 .. ㅎ

전체 코드

#include <iostream>
using namespace std;

int N, cnt;
int board[15];

bool isSetQueen(int row) {
    for (int i=0; i<row; i++) {
        if (board[i] == board[row] || (row - i) == abs(board[row] - board[i])) {
            return false;
        }
    }
    return true;
}

void setQueen(int row) {
    if (row == N) {
        cnt++;
        return;
    }
    for (int i=0; i<N; i++) {
        board[row] = i;
        if (isSetQueen(row)) {
            setQueen(row + 1);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N;
    setQueen(0);
    cout << cnt << "\n";
    return 0;
}

이전 코드

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int chess[16][16];
stack<pair<int, int>> queen;
stack<pair<int, int>> setQueen;

void setLine(int, int, int);
void delLine(int, int, int);
int nQueen(int);

int main() {
	int n;
	cin >> n;
	cout << nQueen(n);
}

void setLine(int x, int y, int n){
	chess[x][y]++;
	for (int i = 1; i <= n; i++) {
		if (i != y) {
			chess[x][i]++;
		}
		if ((x + i) <= n) {
			chess[x + i][y]++;
			if ((y - i) >= 1)
				chess[x + i][y - i]++;
			if ((y + i) <= n)
				chess[x + i][y + i]++;
		}
	}
}

void delLine(int x, int y, int n) {
	chess[x][y]--;
	for (int i = 1; i <= n; i++) {
		if (i != y) {
			chess[x][i]--;
		}
		if ((x + i) <= n) {
			chess[x + i][y]--;
			if ((y - i) >= 1)
				chess[x + i][y - i]--;
			if ((y + i) <= n)
				chess[x + i][y + i]--;
		}
	}
}

int nQueen(int n) {
	if (n == 1) return 1;

	int result = 0;
	int line = 1;
	int x, y, noQueen;

	for (int i = 1; i <= n; i++) {
		queen.push(make_pair(line, i));
	}
	
	while (1) {
		if (setQueen.size() != 0 && queen.size() != 0 && queen.top().first <= setQueen.top().first ) {
			while (1) {
				if (setQueen.size() == 0 || queen.top().first > setQueen.top().first) {
					break;
				}
				x = setQueen.top().first;
				y = setQueen.top().second;
				delLine(x, y, n);
				setQueen.pop();
			}
		}

		x = queen.top().first;
		y = queen.top().second;
		setLine(x, y, n);
		setQueen.push(make_pair(x, y));
		queen.pop();
		line = x + 1;

		noQueen = 0;
		for (int i = 1; i <= n; i++) {
			if (chess[line][i] == 0) {
				queen.push(make_pair(line, i));
				noQueen++;
			}
		}
		if (noQueen == 0) {

		}
		else {
			if (line == n) {
				while (queen.size() != 0 && queen.top().first == n) {
					result++;
					queen.pop();
				}
			}
			
		}
		
		if (queen.size() == 0) {
			break;
		}
	}
	return result;
}