[c++/백준] 9663번: N-Queen

문제 링크

9663번: N-Queen

풀이

유망함수를 이용한 백트래킹 문제

1. board 벡터는 각 인덱스(행)마다 퀸이 위치하는 열의 수가 들어있다.
   1-1. 첫번째 행의 퀸의 위치를 설정하기 위해 반복문을 통해 board[0]을 설정하고 queens(0)을 실행한다.
2. queens(int row)는 현재 실행 중인 행을 나타내고, 그 행에서의 퀸의 위치(board[row])가 유망하다면(공격할 수 없는 위치라면)
   2-1. row == n-1이라면 마지막 행이었다는 뜻이므로 ans++
   2-2. 아니라면 다음 행에서 퀸의 열의 위치를 넣어주고 다시 queens(row+1)을 실행시킨다.
3. 유망한지는 퀸의 열이 같지 않고(행은 다 다르게 설정 했으니), 대각선 위치에 있지 않다는 것으로 판단한다.
   3-1. 현재 행과, 현재 행까지의 행을 비교한다. 대각선은 비교하는 퀸들의 각 열과 행의 뺄셈에서 절대값을 씌워 비교할 수 있다.
   3-2. 유망하다면 true, 유망하지 않다면 반복문을 바로 끊고 false를 return한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n;
int ans = 0;
vector<int> board;

bool promising(int row) { //유망한지 확인
	for (int i = 0;i < row;i++) {
		if (board[row] == board[i] || abs(board[row] - board[i]) == abs(row - i)) {
			return false;
		}
	}
	return true;
}

void queens(int row) { //보드를 확장
	if (promising(row)) {
		if (row == n-1) {
			ans++;
		}
		else {
			for (int i = 0;i < n;i++) {
				board[row + 1] = i;
				queens(row + 1);
			}
		}	
	}
}

int main()
{
	cin >> n;

	board.resize(n);

	for (int i = 0;i < n;i++) {
		board[0]=i;
		queens(0);
	}

	cout << ans;

	return 0;
}