[백준] 9663번 N-Queen

9663번: N-Queen

백트래킹의 대표적인 문제이다.

이차원 배열을 만들 필요 없이 일차원 배열로

인덱스는 행, 값은 열을 넣어주어 풀 수 있다.

 

퀸이 배치될 수 있는 조건은

1. 같은 행에 있지 않을 때

2. 같은 열에 있지 않을 때

3. 같은 대각선 상에 있지 않을 때

이다. 

 

1번의 경우는 queen이라는 일차원 배열을 만듦으로써 행이 겹칠 수가 없게 된다.

2번과 3번의 경우는 인덱스 0부터 현재 행 전까지 돌아가는 for문을 끝까지 돌면서

현재 위치가 queen을 놓을 수 있는 조건인 경우 다음 행(다음 queen)을 위해 recursion 해주고

2번이나 3번의 조건에 한 번이라도 걸리는 경우 queen을 놓을 수 없으므로

break로 빠져나온 뒤 다음 열로 넘어가 다시 검사한다.

#include <iostream>
#include <cstdlib>
using namespace std;
int queen[15], cnt;
void chessBoard(int N, int current) {
	if (current == N) cnt++; //모든 퀸을 배치 했으면 카운트
	else {
		for (int i = 0; i < N; i++) {
			queen[current] = i; //일단 현재 행 배열에 현재 열을 넣어준다
			bool pass = true;
			for (int j = 0; j < current; j++) {
				if (abs(queen[current] - queen[j]) == current - j || queen[j] == queen[current]) { //현재 위치가 다른 퀸의 대각선이거나 같은 열이라면 다음 열에 넣어주기 위해 빠져나온다.
					pass = false;
					break;
				}
			}
			if (pass) chessBoard(N, current + 1); //현재 위치가 알맞은 위치라면 다음 행(다음 퀸)으로 넘어간다.
		}
	}
}

int main() {
	int N;
	cin >> N;
	chessBoard(N, 0);
	cout << cnt;
	return 0;
}