[C++] 백준 9663 : N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

백준 9663번 N-Queen문제를 풀어봤습니다.

처음엔 2차원 배열로 체스판을 만들어서 풀면 쉬울 것 같아서 2차원 배열로 풀었더니 시간 초과가 나왔습니다.

그래서 1차원 배열로 바꾸고 배열의 인덱스를 y좌표, 배열의 값을 x좌표로 가정하고 풀었습니다.

board[1]=2 면 (1,2)에 퀸이 위치한 것입니다.

입력받은 n만큼 순회하면서 해당 level(y좌표)과 i(x좌표)에 퀸을 놓습니다.

그 다음 퀸을 놓아도 되는 좌표인지 확인을 하고 놓아도 되면 다음 level로 백트래킹 함수를 호출합니다.

 

isPromising 함수에서 같은 행에 대해선 체크할 필요는 없습니다.

첫 번째 if문은 같은 열을 체크하는 것이고 두 번째, 세 번째는 대각선을 체크하는 것입니다.

같은 열, 같은 대각선에 퀸이 없으면 true를 반환합니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int board[15];
int result = 0;
int n;

bool isPromising(int level) {
	for (int i = 1; i < level; i++) {
		if (board[i] == board[level])
			return false;
		if ((board[i] - board[level]) == (i - level))
			return false;
		if ((board[level] - board[i]) == (i - level))
			return false;
	}
	return true;
}

void bt(int level) {
	if (n+1 == level) {
		result++;
		return;
	}

	for (int i = 1; i <= n; i++) {			
		board[level] = i;
		if (isPromising(level)) {
			bt(level + 1);
			board[level] = 0;
		}
		board[level] = 0;
	}
}

int main() {
	cin >> n;

	bt(1);
	cout << result;
}