[오답] 백준 9663번: N-Queen (C++)

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

9663번: N-Queen

 

퀸이 올라올 수 없는 곳의 위치를 체스판 한 칸 한 칸으로 관리하려고 했다.

 

그래서 2차원 배열을 활용했는데

 

초반의 생각은 이러했다.

 

가령 1,0에 퀸을 놓으면 1,0이 포함된 행과 열 그리고 두 개의 대각선에 퀸을 놀 수 없다.

 

이때 1,2는 둘 수 없는 위치이다. 그런데 2, 2는 둘 수 있는 위치이고, 2,2에 퀸을 두고 또 2,2를 둠으로써 둘 수 없는 위치를 잡고 나서 재귀를 빠져나올 때, 2,2의 행과 열 그리고 두 대각선의 bool 값을 모두 변경해버리면 1,1가 막고 있었던 것이 풀리게 되어서 제대로 된 연산이 되지 않는다.

 

따라서 좌표 하나하나를 관리할 게 아니라, 열과 행 그리고 대각선들로 사용중 여부를 관리하는 배열을 잡아야 한다.

 

#include<iostream>
using namespace std;
int N, m[15][15];
bool isused[15][15];
int cnt = 0;
void usage(int i, int j, bool ctr) {
	isused[i][j] = ctr;
	if (ctr) {
		printf("퀸위치: %d %d'\n", i, j);
	}
	for (int k = 0; k < N; k++) {
		isused[i][k] = ctr;
		isused[k][j] = ctr;
	}
	for (int l = 0; l < N; l++) {
		for (int m = 0; m < N; m++) {
			if (l + m == i + j) isused[l][m] = ctr;
			if (l - m == i - j) isused[l][m] = ctr;
		}
	}
}
void func(int k) {
	if (k == N+1 ) {
		cnt++;
		
		return;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!isused[i][j]) {
				usage(i, j, true);
				printf("%d %d에 퀸추가\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' '; 
					}cout << '\n';
				}
				cout << '\n'<<'\n';
				func(k + 1);

				//isused[i][j] = false;
				usage(i, j, false);
				printf("%d %d에 퀸제거\n", i, j);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						cout << isused[i][j] << ' ';
					}cout << '\n';
				}
				cout << '\n' << '\n';
			}
		}
	}
}
int main(void) {
	cin >> N;
	func(1);
	cout << cnt << '\n';
	return 0;
}