[C/C++] 백준 9663번 - N-Queen (DFS, 백트래킹)

 

<코드>

#include<iostream>
#include<math.h>
using namespace std;

int N;
bool straight[15]; // 상하 방향
bool diagnol_1[28]; // "/"방향의 대각선
bool diagnol_2[28]; // "\"방향의 대각선
int ans = 0; // 정답


void dfs(int i)
{	
	if (i == N)
	{
		ans++;
		return;
	}
	
	for (int j = 0; j < N; j++)
	{

		if (straight[j] == false &&  // 상하방향으로 퀸이 없을경우
			diagnol_1[i + j] == false && // "/"방향의 대각선으로 퀸이 없을경우
			diagnol_2[i - j + 14] == false) // "\"방향의 대각선 퀸이 없을경우
		{
			straight[j] = true;
			diagnol_1[i + j] = diagnol_2[i - j + 14] = true;

			dfs(i + 1);

			straight[j] = false;
			diagnol_1[i + j] = diagnol_2[i - j + 14] = false;
		}

	}
}

int main()
{
	cin >> N;
	dfs(0);
	cout << ans;
}

 

(엑셀에 담긴 고뇌의 흔적....)

 

풀이는 DFS로 풀었으며 straight[15] 배열의 경우 현재까지 몇열에 퀸이 있는지 표시하는 배열이며
diagnol_1[28], diagnol_2[28] 배열은 각각 대각선에 퀸이 있는지 표시하기 위한 배열이다.

 

straight 배열은 상하방향으로 퀸이 있는지 판별하기 위한 배열이다.

 

diagnol_1 배열의 경우 "/"방향의 대각선내에 있는 좌표의 합이 모두 동일하다는 점을 통해 0에서 최대 28까지의 합이 나올 수 있다. 

 

마찬가지로 diagnol_2 배열의 경우 "\"방향의 대각선내에 있는 좌표의 뺄셈이 모두 동일하다는 점을 통해 -14부터 최대 14까지의 값이 나올 수 있다. 따라서 이를 배열에 표시해주기 위해 14+i-j 번째 배열에 표시를 해준다.

 

 

 

www.acmicpc.net/problem/9663

9663번: N-Queen