[Gold IV] N-Queen - 9663

(N-QUEEN) 문제 링크

성능 요약

메모리: 2020 KB, 시간: 4084 ms

분류

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

제출 일자

2024년 1월 1일 21:59:44

문제 설명

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

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

입력

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

출력

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

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;
int n;
int chess[16][16];

bool isSafe(vector<int>& board, int cnt, int check) {
	for (int past_row = 0; past_row < cnt; past_row++) {
		if (board[past_row] == check || abs(past_row-cnt) == abs(board[past_row]-check)) {//같은 행,열,대각선에 있으면 안됨.
			return false;
		}
	}
	return true;
}

void solve(vector<int>& board, int cnt, long long& ans) {
	//cnt를 행으로 설정
	if (cnt == n) {
		ans++;
		return;
	}
	for (int i = 0; i < n; i++) { //열로 설정
		if (isSafe(board, cnt, i)) {  
			board[cnt] = i;
			solve(board, cnt + 1, ans);
			board[cnt] = -1;
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	vector<int> chessboard(n, -1);
	long long ans = 0;
	solve(chessboard, 0, ans);
	cout << ans << "\n";
}