[SWEA] 2806 N-Queen

2806 N-Queen

풀이)

완전 탐색 문제이고,

퀸이 같은 행, 열 또는 대각선에 놓일 수 없다는 점을 잘 생각해서 풀면 되는 문제이다.

퀸은 같은 행에 놓일 수 없다  

↓

한 행 당 하나의 퀸만 놓일 수 있다. 를 기준으로 

각 행 당 어떤 열에 퀸을 놓을 때, 

이전 행들이 퀸을 놓은 열과 직선인지 

혹은

이전 행들이 퀸을 놓은 열과 대각선인지 

를 확인해서 두 경우에 해당하지 않는 경우에만 퀸을 놓아줬다.

(이전 행들이 퀸을 놓은 열들은 1차원 배열을 통해 저장해줬다.

int row[10] // row[i] = j -> i번째 row j번째 column에 퀸이 놓여졌다.)

코드)

#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
 
int n;
int row[10]; //row[i] = j -> i번째 row j번째 column에 퀸이 놓여졌다. 
int result;
 
void dfs(int idx) {
    if (idx == n) {
        result++;
        return;
    }
    
    for (int i = 0; i < n; i++) { //[idx][i]에 퀸을 놓을 수 있는지 확인
        bool check = false;
        for (int j = 0; j < idx; j++) {
            //이전에 사용한 열과 같은 직선에 있을경우, 혹은 이전에 사용할 열과 대각선위치에 있을경우
            if (row[j] == i || abs(j - idx) == abs(row[j] - i)) {
                check = true;
                break;
            }  
            
        }
        if (check) continue;
        row[idx] = i;
        dfs(idx + 1); // 다음행으로
    }
}
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d", &n);
        dfs(0);
        printf("#%d %d\n", test_case, result);
        result = 0;
    }
    return 0;
}