백준 9663 c++ N-Queen

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

---

#include <iostream>
using namespace std;

int N;
int result;
int col[15];//col[x] = 1 // x행의 queen위치는 1열

bool check(int row)
{
	for (int i = 0; i < row; i++)
	{
		if (col[row] == col[i] || row - i == abs(col[row] - col[i]))//세로, 대각선에 퀸이 있다면 false
			return false;
	}
	return true;
}

void dfs(int row)
{
	if (row == N)
	{
		result++;
		return;
	}
	for (int i = 0; i < N; i++)
	{
		col[row] = i;//일단 해당 row의 i열에 퀸을 넣어보고
		if (check(row))//check함수를 통해 다른 퀸과 안 닿는지 검사
		{
			dfs(row + 1);//통과하면 다음 행으로
		}
	}
    return;
}

int main()
{
	cin >> N;

	dfs(0);
	cout << result;
}