N-Queen

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
10 초	128 MB	91882	44089	28607	46.649%

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

2

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

---

통과된 코드

#include <iostream>
#include <cmath>
using namespace std;
constexpr int Max = 15; // 체스판의 최대 
int _N, _Res, _Queen[Max];

bool CheckQueens(int _row)
{
	for (int i = 0; i < _row; i++) {
		// 절대값으로 대각선으로 전부 확인
		if (_Queen[i] == _Queen[_row] || ( abs(_Queen[i] - _Queen[_row]) == abs(i - _row))) {
			return false;
		}
	}
	return true;
}

void BackTracing(int _row) {
	// N번째까지 왔다면 경우의 수 추가
	if (_row == _N) {
		_Res++;
		return; 
	}

	for (int _col = 0; _col < _N; _col++) {
		_Queen[_row] = _col;
		//해당 행이 가능한지 확인한다.
		if (CheckQueens(_row)) 
			BackTracing(_row + 1);
	}
}

int main()
{
	cin >> _N; // 체스판의 크기 입력
	BackTracing(0); // 백트레킹으로 체크
	cout << _Res;
	return 0;
}

더 효율적인 코드

DFS 탐색을 이용한 백트레킹

dy dx를 대각선으로 표현하여 검사

#include <iostream>
using namespace std;
constexpr int Max = 15;
int _N, _Res;
// 체스판 
bool MapArr[Max];
//체스판의 대각선을 표현하기위한 변수
//대각선은 2N - 1개 필요
bool dx[29], dy[29];

void BackTracking(int level)
{
	if (level == _N) {
		_Res++;
		return;
	}
	for (int i = 0; i < _N; i++) {
		//현재 열, 왼쪽 대각선 및 오른쪽 대각선에 이미 배치된 여왕이 없는지 확인
		// dx, dy는 체스판의 특정한 위치를 나타내는 변수가 아니다.
		// dx, dy를 이용하여 대각선을 추적하는 것
		// 배열의 각 인덱스는 dx대각선을 나타내며 해당 인덱스의 값은 대각선이 여왕에 의해 점유되는지 여부를 나타냅니다. 
		if (!MapArr[i] && !dx[i - level + _N] && !dy[i + level]) {
			
			MapArr[i] = dx[i - level + _N] = dy[i + level] = true;
			BackTracking(level + 1);
			MapArr[i] = dx[i - level + _N] = dy[i + level] = false;
		}
	}
}

int main() {
	_Res = 0;
	cin >> _N;
	BackTracking(0);
	cout << _Res;
}