알고리즘 :: 백준 :: Bruteforce :: 9663 :: N-Queen

문제

문제접근

문제 이해

• Queen의 공격 범위는 가로, 세로, 대각선입니다.
  • 각 행마다 queen은 단 하나만 들어갈 수 있습니다.
  • 각 열마다 queen은 단 하나만 들어갈 수 있습니다.
  • 모든 행마다 queen을 넣었을 때 대각선을 고려해줘야 합니다.
• 외부 배열 row[N], leftDig[2 * N - 1], rightDig[2 * N - 1]을 만듭니다.
• 0 ~ N - 1번째 행을 모두 검사하며 i번째 열에 queen을 넣었다면, 그 queen으로부터 대각선에 있는 모든 칸에는 queen이 들어갈 수 없습니다.

• 재귀함수는 go(cnt) 형태이며, 이때 cnt는 열과 동일한 의미를 가집니다.
• r번째 행에 대해 만일
  • row[r] == true이면 해당 행에는 이미 queen이 있다는 의미입니다.
  • leftDig[N - 1 + r - cnt] == true이면 (r, cnt)에 queen을 두려고 했는데 왼쪽 대각선을 살펴보니 이미 queen이 있다는 의미입니다.
  • rightDig[r + cnt] == true이면 (r, cnt)에 queen을 두려고 했는데 오른쪽 대각선을 살펴보니 이미 queen이 있다는 의미입니다.

코드

#include <iostream>
using namespace std;

int N, ans;
bool row[15], leftDig[29], rightDig[29];

void go(int cnt) {	// cnt == col
	if (cnt == N) { ans++; return; }
	for (int r = 0; r < N; ++r) {
		if (row[r] || leftDig[N - 1 + r - cnt] || rightDig[r + cnt]) continue;
		row[r] = leftDig[N - 1 + r - cnt] = rightDig[r + cnt] = true;
		go(cnt + 1);
		row[r] = leftDig[N - 1 + r - cnt] = rightDig[r + cnt] = false;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	go(0);
	cout << ans;
}

결과