백준 BOJ 9663 - N-Queen

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

9663번: N-Queen

웰노운인 N퀸문제이다.

백트래킹 기법을 사용해 풀수 있었다.

 

func함수에서 탐색을 담당하는데

board배열은 각 행당 몇번째 열에 퀸이 들어가는가를 저장한다.

일단 k번째 열(처음에는 0번째열)의 i번째 열에 퀸을 배치해보고

chk함수를 통해서

같은 열에 퀸이 있는가? 와

대각선상에 퀸이 있는가? 를 판별한다

대각선상에 퀸이 있는지를 판별하기 위해서는

board[i]-board[k](열간의 거리) = k-i(행간의 거리) 로 판별할 수 있는데 이는

열간의 거리와 행간의 거리가 같은지 비교해서 대각선상에 있는지를 판별한다.

근데 다른 방향으로의 대각선도 비교를 해줘야 하므로

열간의 거리에 절댓값을 씌워주었다.

이러면 열간의 거리에 음수값이 걸려도 양수로 변환되서 양쪽 대각선 모두 다 판별할 수 있다.

 

#include <stdio.h>
#include <math.h>

int board[20] = {0};
int n;
int ans = 0;

bool chk(int k){
	for(int i=0; i<k; i++) if(board[k]==board[i] || abs(board[i]-board[k])==k-i) return false;
	return true;
}

void func(int k){
	if(k==n){ ans++; return; }
	for(int i=0; i<n; i++){
		board[k] = i;
		if(chk(k)) func(k+1);
	}
}

int main(){
	scanf("%d", &n);
	func(0);
	printf("%d", ans);
	return 0;
}