[백준 알고리즘][백트래킹] 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);

}

}