NQueen - 정올 1889번

정올 1889번 NQueen문제의 답

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162&sca=3030

backtracking을 활용한 것이다.

backtracking이란.. dfs를 통해 구현하는 중에 가지치기를 진행하는 수법이라고 한다.

#include <stdio.h>

#include <stdlib.h> //abs 함수를 사용하기 위해서임

int promising(int); // 할만한지 안한지 체크하는 함수. 

int n;

int col[255] = { 0, }; // 행에 놓이는 값. 예를 들어 col[1] = 5라면 2번째 에는 5번째에 있다는 내용임

int cnt =0; // 해결되는 값

void queens(int i) {

if (promising(i))

{

if (i == n)

{

cnt++; // 총 개수를 구함

}

else

{

for (int j = 1; j <= n; j++) {

col[i + 1] = j;

queens(i + 1);

}

}

}

}

int promising(int i) { // 직선, 대각선으로 만나는지 검사

int k = 1, promising = 1;

while (k < i && promising) {

if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k)) //직선이나 대각선상에 있는가를 검사

{

promising = 0;

}

k++;

}

return promising;

}

int main() {

scanf("%d", &n);

queens(0);

printf("%d", cnt);

}