백준 9663번: N-Queen

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

9663번: N-Queen

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 15

char check(char arr[], int row){
    int i;
    for(i = 0; i< row; i++)
        if(arr[row] == arr[i] || abs(row-i) == abs(arr[row] - arr[i]) )
            return 0;
    return 1;
}
int N_Queen(char arr[], int n, int row){
    int i, cnt = 0;
    
    if(row == n) return 1;
    
    for(i=0;i<n;i++){
        arr[row] = i;
        
        if(check(arr, row))
            cnt += N_Queen(arr, n, row+1);
    }
    return cnt;
}

int main()
{
    int n;
    char chess[MAX_N] = {0,};
    scanf("%d", &n);
    printf("%d", N_Queen(chess, n, 0));
    
    return 0;
}

Queen의 행동반경에 겹치는 다른 Queen이 있는지 확인하는 수식을 이해한다면 쉽게 풀 수 있다.

대각선에 있는지 검사하는 수식은 가로행의 차와 세로행의 차가 동일하다면 대각선에 존재한다는 의미이다. 처음 이 수식이 이해되지 않아 n*n 2차원배열을 만들어서 직접 검사하기도 하고, 절댓값을 사용하는 게 이해되지 않아 모든 대각선을 검사하기 위해 ++,--, +-,-+의 경우를 확인해보기도 했다. 이처럼 알고리즘의 수행시간을 줄이기 위해서 다양한 시도를 해보고 직접 코딩해 보는 것을 추천한다.