[9663번] N-Queen

9663번: N-Queen

 

www.acmicpc.net

대표적인 백트래킹 문제

N개의 퀸을 N * N 크기의 체스판에 서로 공격이 닿지 않게 놓는 문제다.

이 문제를 풀 때 생각 해야할 점은

1. 이 전에 퀸을 놓았던 행에는 놓을수 없다 --> 각 행 마다 놓을수 있는 퀸의 개수는 1개

2. 이 전에 퀸을 놓았던 열에는 놓을 수 없다. --> 각 열 마다 놓을 수 있는 퀸의 개수는 1개

3. 이 전에 놓았던 퀸의 대각선 범위에는 놓을 수 없다.

기준을 행으로 잡았을 때, 2차원 배열이 아닌 1차원 배열을 이용해서

배열의 인덱스는 행의 위치, 배열의 원소는 그 행에서 놓여진 열의 위치로 표현할 수 있다.

또한 주의 할 점은 맵에 퀸의 공격범위를 하나하나 넣지 말고 규칙을 찾아서 해결해야한다.

Q1(a.b)와 Q2(c.d)가 있다고 하면

두 퀸이 대각선 위치에 겹치는 규칙은 |a-c| == |b-d| 다.

/*9663번 N-Queen*/
#include <iostream>
#include <math.h>
using namespace std;
int N, cnt;
int Q_loc[15];
bool promising(int r, int c) {//r,c는 현재 놓고 싶은 위치
	if (r == 1) return true;
	else {
		for (int i = 1; i < r; i++) { // i: 현재 놓고 싶은 행의 이전 행들
			if (c == Q_loc[i] || abs(r-i) == abs(c - Q_loc[i])) return false; 
		}
		return true;
	}
}
void put_Q(int now_row) {
	if (now_row > N) {
		cnt++;
	}
	else {
		for (int c = 1; c <= N; c++) {
			if (Q_loc[now_row] == 0 && promising(now_row, c) == true) {
				Q_loc[now_row] = c;
				put_Q(now_row + 1);
				Q_loc[now_row] = 0;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	put_Q(1);
	cout << cnt;
}