[9663] N-Queen

문제

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

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

입력

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

출력

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

코드

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

int N;
int ans = 0;
int col[16];
bool temp;

void nqueen(int x) {
	if(x==N){
		ans++;
		return;
	}

	for(int i=0; i<N; ++i){
		temp = true;
		col[x] = i;
		
		for(int j=0; j<x; ++j){
			if(col[x] == col[j] || (abs(x-j) == abs(col[x]-col[j]))){
				temp = false;
				break;
			}
		}

		if(temp){
			nqueen(x+1);
		}
	}

}

int main() {
  cin >> N;

  nqueen(0);

  cout << ans;

  return 0;
}

문제만 보면 간단한거 같으면서도...? 쉽지 않은 문제이다.

나는 처음 이 문제를 보자마자 무식하게 이차원 배열의 모든 좌표에 퀸을 놓았을 때 겹치지 않을 때의 경우의 수를 구하려 했다.

그래서 0,0 부터 N,N까지 퀸을 대입해보면서 풀려 하였는데 막상 해보니 쉽게 나오질 않았다...

1시간의 사투 결과 힌트를 보게 되었다....

위 그림과 같이 퀸이 겹치지 않는 경우의 수를 곰곰히 생각해보면,

1. 한 줄에 퀸을 한개만 놓을 수 있다.

2. 대각선으로 퀸이 겹치면 안된다.

이 두가지 수만 충족시키면 퀸의 배치가 완성된다.

1번의 경우 구하기 쉽고 2번이 문제인데 2번은 (x좌표의 차이 == y 좌표의 차이) 이렇게 풀면 쉽게 풀린다.

 

문제를 풀어보기 전에 한번 생각해보는 시간을 가져보자!