8. 1889 : N Queen [DFS]

문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162&sca=50&sfl=wr_subject&stx=queen&sop=and

JUNGOL | N Queen > 문제은행

문제 풀이 :

#include <stdio.h>
int chess[13 + 10][13 + 10];
int N;
int sol = 0;
int check(int y, int x) {
	int i, j;
	for (i = 0; i < y; i++) if (chess[i][x] == 1) return 0;
	for (i = y - 1, j = x + 1; ((i >= 0) && (j < N)); i--, j++)if (chess[i][j] == 1)return 0;
	for (i = y - 1, j = x - 1; ((i >= 0) && (j >= 0)); i--, j--)if (chess[i][j] == 1) return 0;

	return 1;
}
void N_Queen(int y) {
	int j;
	if (y >= N) { sol++; return; }
	for (j = 0; j < N; j++) {
		if (check(y, j) == 1) {
			chess[y][j] = 1;    //재귀 호출 전 set
			N_Queen(y + 1);
			chess[y][j] = 0;    //재귀 호출 후 clear
		}
	}
}
int main() {
	scanf("%d", &N);
	N_Queen(0);
	printf("%d\n", sol);
}

 

일단 배치한 뒤 조건이 만족 안되면 백트래킹을 해가면서 마지막으로 배치 성공한 부분부터 다시 시작한다.