[SW Expert] #2806 N-Queen

https://swexpertacademy.com/main/main.do

SW Expert Academy

---

1. 해결방법

어떤 방법으로 해결을 할 수 있을지 몰라서 결국 문제를 찾았다 DFS를 활용한 백트래킹 방법으로 이를 해결하는 방법이 가장 일반화 되어있었고, DFS에서 가지치기를 하는방법이다.

---

2. 에러사항

가지치기를 하는 부분에서 예를들어 1행 1열에 체스가 놓여져 있다고 하면 2행에는 1행에놓여진 열, 열-1, 열+1 이 세가지를 피하면 해결 될 것이라고 생각했으나 이는 대각선을 처리하는 부분에 문제가 있었다. 대각선을 처리하는법은 행끼리의 차이와 열끼리의 차이가 같으면 대각선으로 판단하는 방법으로 해결했다.

---

3. 코드

#include <iostream>
#include <string.h>
#include <cmath>
using namespace std;

int total;
int num;
int col[15];
int cnt;

bool check(int val) {

	for (int i = 1; i < val; i++) {
		if (col[i] == col[val]) {
			return false;
		}
		if (abs(val - i) == abs(col[val] - col[i])) {
			return false;
		}
	}

	return true;
}

void dfs(int row, int co) {

	if (row == num) {
		cnt++;
	}
	else {
		for (int i = 1; i <= num; i++) {
			col[row + 1] = i;
			if (check(row + 1)) {
				dfs(row + 1, i);
			}
			else {
				col[row + 1] = 0;
			}
		}
	}
	col[row] = 0;
}

int main()
{
	scanf("%d", &total);
	for (int i = 0; i < total; i++) {
		memset(col, 0, sizeof(col));
		cnt = 0;
		scanf("%d", &num);
		for (int j = 1; j <= num; j++) {
			col[1] = j;
			dfs(1, j);
		}
		cout << "#" << i+1 << " " << cnt << endl;
	}
}