백준 9663번 N-Queen // C++

문제

 

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

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

입력

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

출력

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

 

---

 

풀이

 

N-Queen 문제는 대표적인 Back Tracking 문제이다.

 

체스에서 Queen은 가로, 세로, 대각선 중 원하는 방향으로 쭉 움직일 수 있다.

초록색과 같은 위치에 Queen이 놓이게 되면, 파란색으로 칠해진 가로 세로 대각선 방향에는 다른 Queen을 놓을 수 없게 된다.

 

이 때, Queen을 n개만큼 놓을 수 있는 경우의 수를 모두 출력하면 된다.

 

dfs와 비슷한 느낌으로 풀면 되는데, 이 때까지 놓인 모든 Queen과 하나씩 비교하면서 같은 방향이 아닌 경우에만 하나씩 추가하면서 n개가 되면 카운트 해주면 된다.

---

 

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n; // board size
vector<pair<int, int>> v; // queen's location
int ans = 0;

void nQueen(int num);

int main() {
	cin >> n;

	nQueen(0);

	cout << ans;
}

void nQueen(int num) {
	if (num == n) {
		ans++;
		return;
	}

	vector<pair<int, int>> temp = v;
	bool check;

	for (int i = 0; i < n; i++) {
		check = true;
		for (int j = 0; j < temp.size(); j++) {
			int x = temp[j].first;
			int y = temp[j].second;

			if ((x == i) || (y == num) || (abs(x - i) == abs(y - num))) { // 가로가 같거나 || 세로가 같거나 || 대각선이 같은 경우
				check = false;
					break;
			}
		}

		if (check) {
			v.push_back(make_pair(i, num));
			nQueen(num + 1);
			v.pop_back();
		}
	}
}