[백준] N-Queen (9663번)

문제

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

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

입력

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

출력

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

---

백트래킹의 조상격인 n퀸 문제이다. 

오랜만에 풀었더니 좌표를 2차원 배열로해서 다시풀었다.

 

1차원 배열로 해서 각 행마다 어디에 퀸을 놓을 지 기록한다.

 

각 행마다 각 열에 퀸을 하나씩 놓아도 되는지 isTrue로 조사한 후 가능하다면 퀸을 놓는다.

isTrue는 이전 행까지 같은 열에 놓은 퀸이 있는지, 대각선으로 놓은 퀸이 있는지를 조사해서 있다면 false를 반환한다.

그렇게 N번 행까지 모두 퀸을 놓았다면 결과값을 1 늘리고 return 한다.

 

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/N-Queen%20(9663%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;
int N, res;
int p[17];

bool isTrue(int x, int y) {
	for (int i = 1; i < x; i++) {
		if (p[i] == y) return false;
		if (abs(y-p[i]) == x-i) return false;
	}
	return true;
}

void queen(int x, int y) {
	p[x] = y;

	if (x == N) {
		res++;
		p[x] = 0;
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (isTrue(x + 1, i)) {
			queen(x + 1, i);
		}
	}

	p[x] = 0;
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++) 
		queen(1, i);

	cout << res;
}