문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8 |
예제 출력 1
92 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int abs(int N)
{
return N<0?-N:N;
}
int queen(int *board,int current,int N)
{
int count=0, *temp=calloc(N,sizeof(int));
if(current==N)
{
free(temp);
return 1;
}
for(int i=0;i<current;i++)
temp[i]=board[i];
for(int n=0;n<N;n++)
{
bool flag=true;
for(int i=0;i<current;i++)
if(board[i]==n || current-i==abs(n-board[i]))
{
flag=false;
break;
}
if(flag)
{
temp[current]=n;
count+=queen(temp,current+1,N);
}
}
free(temp);
return count;
}
int main(void)
{
int N, *board=NULL;
scanf("%d", &N);
board=(int *)calloc(N,sizeof(int));
printf("%d\n", queen(board,0,N));
free(board);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 20152번: Game Addiction(틀림) (0) | 2021.01.24 |
---|---|
<백준 알고리즘> 20540번: 연길이의 이상형 (0) | 2021.01.24 |
<백준 알고리즘> 11052번: 카드 구매하기 (0) | 2021.01.22 |
<백준 알고리즘> 16483번: 접시 안의 원 (0) | 2021.01.22 |
<백준 알고리즘> 1463번: 1로 만들기 (0) | 2021.01.09 |