[백준 알고리즘][백트래킹] 9663번 N-Queen
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력 및 출력
첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력은 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
문제 출처 : 백준 온라인 저지 https://www.acmicpc.net/problem/9663
풀이
퀸을 놓을 때 규칙은 같은 가로줄, 세로줄에 놓을 수 없고 대각선으로 같은 줄이어도 놓을 수 없다. 퀸을 하나씩 놓아보며 모든 경우를 찾아보고 만약 놓을 수 없을 경우는 바로 다른 곳에 놓도록 한다. 제일 윗줄부터 차례대로 놓고, 놓은 퀸들은 배열에 저장해두고, 놓을 수 없는 경우 돌아가며 새로 퀸을 저장할 수 있게 해야한다. 만약 체스판에서 i, j에 퀸이 놓여있다고 치면, 새로운 퀸 x, y에서 i != x 이어야하고 j != y이어야한다. 또 대각선으로 만나면 안되니까 i-x != j-y 이어야한다.
promising function 은 위의 조건 3가지임을 알겠는데, 이 조건을 어떻게 처음부터 검사하고 계속 조건을 만족해서 N개의 퀸이 놓여졌을 때 카운트를 해줘야할지 모르겠다.
for문이 main에서도 돌아가고 backtrack 함수안에도 넣어서 어떻게 보면 이중for문의 형태로 모든 N*N 체스판에 퀸을 놓아볼 수 있도록 구현했다.
코드
#include<stdio.h>
#include<math.h>
int queen[16]; //각 줄의 퀸을 저장
int N;
int cnt;
void backtrack(int x);
void main()
{
int i, j;
scanf("%d", &N);
for(i=0; i<N; i++) //0번째 줄에 하나씩 퀸을 놓아본다
{
queen[0] = i;
backtrack(0);
}
printf("%d\n", cnt);
}
void backtrack(int x) //파라매터는 퀸을 놓을 좌표
{
int i, j;
//이자리에 퀸을 놓을 수 있는가?
for(i=0; i<x; i++)
{
if((queen[i] == queen[x]) || (abs(queen[i]-queen[x]) == abs(i-x)) ){
return ;
}
}
if(x == N-1){
cnt++; //퀸을 다 놓은 경우
return ;
}
for(i=0; i<N; i++) //x+1번째 줄에 하나씩 퀸을 놓아본다
{
queen[x+1] = i;
backtrack(x+1);
}
}