[백준] 9663. N-Queen (C++)

Key

• 퀸은 상,하,좌,우, 대각선으로 칸 개수와 상관없이 이동할 수 있다. 따라서 한 행에는 퀸이 하나만 있어야하고 열도 마찬가지다. 
• 따라서 N*N 체스판에 N개의 퀸을 놓는다는 건 모든 행에 하나의 퀸이 있어야된다는 것이다.

 

 

 

Idea

같은 로직을 여러번 반복하며 조건에 맞는걸 찾는다는 점에서 백트래킹이라는 것을 눈치챘다.

처음엔 N*N 배열을 만들어서 풀어야하는건가 했지만, row[열]에 행 값을 할당하는 방식으로 1차원으로 풀었다.

 

1. 재귀함수 check은 행에 퀸을 놓는다.

2. check는 현재 행을 인자로 받아 모든 열에 퀸을 놓는다.

3. 퀸을 놓을 수 있는 경우 다음 행으로 check를 재귀호출한다.

4.  N개의 퀸을 모두 넣었다면 (인자값이 N과 같다면) 카운트한다.

 

바로 이전 행이랑만 검사하는게 아니고 모든 이전 행이랑 검사해야된다는 점을 유의해야한다.

대각선의 경우 x변화량과 y변화량이 같으면 대각선 범위 안이라는걸 이용해서 수식을 세우면 된다.

 

 

Code

#include <iostream>
#include <math.h>
using namespace std;


int N = 0;
int row[15] = { 0, };
int cnt = 0;

// x는 행
void check(int x) {

	// 마지막 행까지 탐색한 경우
	if (x == N) {
		cnt++;
		return;
	}


	// 0열~n열까지 모든 이전 행들을 검사 후 조건에 맞으면 다음 행에 퀸 놓기
	for (int i = 0; i < N; i++) {
		bool isSafe = true;

		row[x] = i;

		// 모든 이전 행
		for (int j = 0; j < x; j++) {
			if (row[x] == row[j] || abs(x - j) == abs(row[x] - row[j])) {
				isSafe = false;
				break;
			}
		}

		if (isSafe) {
			check(x + 1);
		}
	}

}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	check(0);

	cout << cnt << "\n";

	return 0;
}