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

문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

.
.
.
풀이

백트래킹이다.
이제야 백트래킹과 그냥 깊이 우선 탐색의 차이가 분명해지는 듯!
백트래킹은 답을 정해놓고 다음 답을 찾아나가면서 푸는 것이고,
깊이 우선 탐색은 뻗어져 나갈 수 있는 가지를 전부 탐색하는 것.
어렴풋하던 것이 이제야 와닿는다.

#include <iostream>
using namespace std;

int N;
int ans = 0;
int chess[15];

bool Ch(int l)
{
	// 퀸은 상하좌우 대각선으로 움직일 수 있으므로,
	// 서로 공격하지 못하려면
	// 같은 행, 같은 열에는 하나의 퀸만이 들어가야 한다.
	// 대각선의 경우, 두 점의 x, y 좌표 값 차이의 절대값이 일정하다.
	// 이 경우에는 좌상, 우상 방향만 점검하면 됨 (아직 배치하지 않은 아래쪽은 볼 필요 없음)

	// 현재까지 배치된 것 중 공격 당할 수 있는 것 체크
	for (int i = 0; i < l; i++)
	{
		// 같은 열에 배치된 것이 있는지, 대각선이 있는지 체크
		// i, l 은 행의 값이고, chess[i], chess[l]은 열의 값이므로
		if (chess[i] == chess[l] || l - i == abs(chess[i] - chess[l]))
		{
			return false;
		}
	}
	return true;
}

void NQueen(int x)
{
	// N개 배치 완료된 경우 가능한 경우의 수라서 추가
	if (x == N)
	{
		ans++;
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			// 주어진 행에 퀸 배치, 
			// x는 행의 값 i값은 몇 번째 열에 들어있는지를 저장하는 값이 된다.
			chess[x] = i;

			// 현재 위치에 배치가 가능하다면 다음행으로,
			// 안된다면 다시 다음 자리에 퀸 배치
			if (Ch(x))
			{
				NQueen(x + 1);
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	NQueen(0);

	cout << ans;

	return 0;
}