BOJ 9663 (N-Queen)

• 문제
  N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
  N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 N이 주어진다. (1 ≤ N < 15)
  
  
• 출력
  첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

#include<iostream>
#include<queue>
using namespace std;
int N;
int board[15];
int cnt;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

bool isPossible(int num)
{
	bool flag = true;
	for (int i = 0; i < num; i++)
	{
		// 같은 열에 있거나 || 대각선에 있는 것 잡는 부분 (대각선은 x증가량과, y증가량이 같다는 성질 이용)
		if (board[num] == board[i] || num - i == abs(board[num] - board[i]))
		{
			flag = false;
		}
	}
	return flag;
}

void nqueens(int depth)
{
	if (depth == N) cnt++;
	else
	{
		for (int i = 0; i < N; i++)
		{
			// 해당 깊이에서 하나씩 넣어보는 작업
			board[depth] = i;
			if (isPossible(depth))
			{
				// 다음 깊이로 이동 (끝까지 가서 아무일도 없으면 i값이 증가하여 backtracking이 된다.
				nqueens(depth + 1);
			}
		}
	}
}

int main()
{
	fast_io();
	cin >> N;
	nqueens(0);
	cout << cnt;
	return 0;
}

   아주 유명한 N-Queens 문제이다. 입력의 크기가 작고 10초나 주어져 처음엔 이차원 배열을 이용하여 브루트 포스 알고리즘을 생각했는데 1차원 배열로도 상당히 오랜 시간이 소요된다.

퀸의 공격방향인 +뱡향과 대각선 방향을 체크해야하고 board[n] 배열을 통해 퀸이 n 행의 board[n]열에 놓임을 표현했다.

재귀 함수 호출을 통해 백트래킹이 가능하다.

골드문제는 아직도 어렵다..

시간 복잡도 : O(N!)