9663 N-Queen

문제 링크

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

풀이

NxN 체스판에 N개의 퀸을 겹치지 않게 놓으려면 한 행당 하나의 퀸만 놓아야 한다. 그렇지 않으면 가로축에서 무조건 퀸끼리 공격할 수 있게 되기 때문이다. 중요 ) 즉 굳이 for문 두개를 돌려서 체스판 전체를 검사할 필요가 없고, 각 행당 퀸이 몇 번째 열에 놓여있는지만 저장해도 된다는 뜻이다. 퀸이 놓인 열의 정보를 저장할 1차원 배열 board를 사용한다. 0번 인덱스부터 시작하면 된다. putQ에서는 반복문을 돌면서 n번째 행의 i번째 열에 퀸을 놓을 수 있는지 없는지 검사하고(열이 겹치지 않는지, 대각선에서 만나지 않는지(열끼리의 차, 행끼리의 차의 절대값이 같으면 만나게 됨)), 놓을 수 있다면 다음 행으로 넘어갈 수 있도록 n을 1 증가시키고 putQ에 넣어 재귀가 돌아가도록 한다. 만약 n이 N과 같아진다면 N개의 퀸을 전부 놓은 것이므로 ans를 1 증가시키고 함수를 종료한다. 마지막에 ans를 출력하면 된다.

C++코드

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

using namespace std;

int N;
int board[15];
int ans = 0;

void putQ(int n){
	if(n == N){
		ans++;
		return;
	}
    for(int i=0; i<N; i++){
    	board[n] = i;
    	bool check = true;
    	for(int i=0; i<n; i++){
			if(board[i] == board[n] || n-i == abs(board[n] - board[i])){
				check = false;
				break;
			}
		}
    	if(check){
    		putQ(n+1);
		}
	}
}

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