[Jungol] 정올 1889 N Queen

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

 Input 
4

 Output 

2

N이 4일 때, 나오는 경우는 두 가지이다.

 

한 행에 놓을 수 있는 여왕말의 개수는 1개 입니다.

그렇기 때문에 행마다 DFS 탐색을 하면서 1~N까지의 열에 놓을 수 있는지를 확입합니다.

chk_vertical[i] =  i 열에 여왕 존재 여부

 

check_diagonal_1[row + i] = 아래 그림의 대각선은 위치가 (x, y)일 때, 

(5, 5) ↔ (4, 6) ↔ (6, 4) ▶ x + y가 같습니다. check_diagonal_1[10] = 1에 해당

 

check_diagonal_2[row - i + N] = 아래 그림의 대각선은 위치가 (x, y)일 때, 

ex) (5, 5) ↔ (6, 6) ↔ (4, 4) ▶x - y가 같습니다. check_diagonal_1[N] = 1

    ※ (2, 3)과 같이 2 - 3 = -1로 인덱스 접근시 overflow 발생할 수 있으므로 +N 해줍니다.

즉, 행을 한 단계씩 내려가면 각 열마다 여왕말을 놓을 때,

세로선과 대각선상에 다른 여왕말이 있는지를 확인합니다.

(행을 따라 DFS 탐색하기 때문에 같은 행에 여왕말을 놓는 경우는 고려하지 않아도 됩니다.)

 

다른 유사 풀이: [BOJ] 9663 N-Queen

[BOJ] 백준 9663 N-Queen

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int LM = 16;
int N, ans;
int chk_vertical[LM];
int check_diagonal_1[LM * 2];
int check_diagonal_2[LM * 2];
void DFS(int row) {
    if (row > N) {
        ans++;
        return;
    }
    
    // row행에 각 열(col)에 여왕을 놓을 수 있는지 확인합니다.
    for (int i = 1; i <= N; i++) {
        if (chk_vertical[i]) continue; // 세로
        if (check_diagonal_1[row + i]) continue; // 좌상단 대각선
        if (check_diagonal_2[row - i + N]) continue; // 우상단 대각선
        chk_vertical[i] = check_diagonal_1[row + i] = check_diagonal_2[row - i + N] = 1;
        DFS(row + 1);
        chk_vertical[i] = check_diagonal_1[row + i] = check_diagonal_2[row - i + N] = 0;
    }
}
int main(void) {
    scanf("%d", &N);
    DFS(1);
    printf("%d", ans);
}