BOJ 9663, N-Queen
ProblemSolving ·이 문제는 재귀호출을 이용한 완전탐색문제입니다.
풀이
열을 매개 변수(i)로 사용한다. 한번 퀸을 놓은 열은 다시 사용될 수 없기 때문에
첫번째 열부터 재귀호출하여 열이 n보다 커지게 되면 답을 카운트해주면 된다..
그것을 이용하면 한 번의 포문만 재귀호출을 하면 답을 구할 수 있다.
단 사용되지 않았던 행과 대각선에서만 재귀호출이 가능하다.(다음 퀸을 놓을 수 있다)
행의 경우에는 col배열 하나만 선언하면 되지만
왼쪽 위에서 오른쪽 아래로 내려오는 대각선의 경우에는 항상 i-j가 같은 값을 가지고
오른쪽 위에서 왼쪽 아래로 내려오는 대각선의 경우에는 항상 i+j가 같은 값을 가진다.
이것을 재귀호출시마다 체크해주면 답을 구할 수 있다.(i-j는 최대 -13의 음수를 가지므로 13을 더해준다.)
#include<stdio.h>
int n, col[15],x[2][30], ans;
void dfs(int i)
{
if (i > n)
ans++;
for(int j=1; j<=n;j++)
if (!col[j] && !x[0][i - j + 13] && !x[1][i + j])
{
col[j] = x[0][i - j + 13] = x[1][i + j] = 1;
dfs(i + 1);
col[j] = x[0][i - j + 13] = x[1][i + j] = 0;
}
return;
}
int main() {
scanf("%d", &n);
dfs(1);
printf("%d\n", ans);
return 0;
}