[백준/BOJ] 백준 9663번 : N-Queen

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

9663번: N-Queen

 

퀸은 상, 하, 좌, 우, 대각선 모든 방향으로 원하는 만큼 이동 가능하므로, 기본적으로 각 행에는 퀸이 하나씩 있어야 하는 건 명확하므로, 각 행에 퀸을 하나씩 두면서, 행에 어떤 열에 둘지 확인한다. 열을 고를 때, 그 열에 두면 이전에 두었던 퀸과 공격할 수 있는 위치에 있지 않은지 확인하면서 해당 열에 둘 수 있는지 확인했다.

 

코드

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

//퀸은 상,하,좌,우,대각선 모든 방향으로 원하는 만큼 이동 가능
//N*N 크기 체스판에 N개의 퀸을 놓으려면 각 행마다 퀸이 하나씩 존재햐야 한다

int n;
int result = 0;

//point에 퀸을 놓을 수 있는지 확인
bool check(vector<pair<int, int>>& selected, pair<int, int> point) {
	for (int i = 0; i < selected.size(); i++) {
		//selected[i]와 같은 열일때
		if (selected[i].second == point.second) {
			return false;
		}

		//selected[i]와 같은 대각선일때 (좌표간 기울기 절댓값이 1인지 확인)
		if (abs((selected[i].second - point.second)) - abs((selected[i].first - point.first)) == 0) {
			return false;
		}
	}

	return true;
}

void solve(int row, vector<pair<int, int>>& selected) {

	//모든 열을 하나씩 채웠을때
	if (row == n) {
		result++;
		return;
	}

	//row행을 j열로 채우는 경우 확인 
	for (int j = 0; j < n; j++) {
		pair<int, int> point = make_pair(row, j);

		if (check(selected, point)) { //row행에 j열을 놓을 수 있을때
			selected.push_back(point);
			solve(row + 1, selected);
			selected.pop_back();
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	vector<pair<int, int>> selected;
	solve(0, selected);

	cout << result << "\n";

	return 0;
}