[백준 C++] 9663 N-Queen, 백트래킹

문제

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

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

입력

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

출력

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

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

이런경우 DFS로 풀수있으나, 조건이빡세므로 DFS로 모든경우를 탐색하는것은 비효율적이다.

따라서 DFS에 조건을 달아서 조건에맞지않으면 깊이탐색을 종료하는 백트래킹기법을 사용하면된다.

구현할함수는 퀸의 위치가 문제조건에적합한 행,열인지 판단하는 bool함수하나,
그리고 DFS에근거하는 본체함수하나이다.
이 본체함수에서 bool함수로 체크하여 가능한경우에만 자기자신(행+1)을 호출하는 DFS구조를 구현하면됬다.
여기서 사용할 퀸의위치는
queen[row] = col 로 1차원배열에 행과 열의 위치를 기록하였다.

항상 DFS에서 쓰는 구조인게

1. DFS함수 제일처음에 등장하는 조건문으로 모든탐색완료후 조건에맞다면 결괏값을 +1 하고 탈출하게하는 조건문
2. 원하는 로직을 구현한뒤 자기자신을 재귀적으로 호출하도록
   DFS(더깊이들어가는 값)을 호출하게하는것..
3. 마지막으로 호출되고나서 사후처리가필요하다면 사후처리하는코드를 작성하면 되겠다.
4. (백트래킹사용시) 자기자신을 재귀적으로 호출하는 DFS(깊이가는값)에 조건을 달면된다.

이문제는 DFS(int row)로 선언, DFS(1)을 호출하여
1번의 경우 조건문을 row == n(입력값) 으로 끝까지탐색했는가를 체크.
2번의경우는 아래 코드에서
3번은 처리할것이없다. (코드에서 보면 알겠지만 for문에서 열의값을 하나씩 바꿔가며 처리하기때문에 그때그때 초기화가 되는 꼴이다.)
4번으로 for문내에서 해당 행,열위치에 퀸을 놓을수있다면탐색을 이어나가도록 코드를 짰다.

#include <bits/stdc++.h>
using namespace std;

int n, *queen, result;

bool promisingCheck(int row) {//해당 행, 열에 퀸을 놓을수 있는가
	for (int i = 0; i < row; i++) { //입력받은행까지탐색
		if ((queen[i] == queen[row]) || //열의위치가 겹치거나 대각선인경우 불가능함
			//행의위치가 겹칠일은 없으니까 제외함. 말이안되지
			(row - i == (abs(queen[row] - queen[i])))) {
			return false;
		}
	}
	return true;
}

void n_queen(int row) {
	if (row == n) { //n행까지 퀸을 모두 놓았따면 경우의수 +1
		result++;
		return;
	}
	else {
		for (int col = 0; col < n; col++) {
			//행을고정하고 열을 하나씩바꾸면서 가능하면 
			//더 깊이 탐색을하는 DFS에 유망한노드여야만 탐색을하는
			//백트래킹이되겠다.
			queen[row] = col; //row행 col열에 퀸을 놓는다.
			if (promisingCheck(row)) //현재위치가 퀸의 위치로 알맞다면 다음 행을 검사한다.
				n_queen(row + 1); //이게 실행안되면 탐색은종료고, 경우의수는 카운트되지않는다.
		}
	}
}

int main(void) {
	cin >> n;
	queen = new int[n];

	n_queen(0);
	cout << result;

	return 0;
}