9663 N-Queen

9663 N-Queen

백트래킹 처음 입문할 때 배웠지만 이해하지 못했었다.

1차원배열을 이용해서 문제푸는것이 특히 이해되지 않았었는데, 

실력이 많이 늘긴 했는지 생각보다 쉽게 풀었다... 

1. isPromising 함수를 이용해 다음점이 놓을 수 있는 점인지 체크한다.

-> 대각인경우는 가로의차이==세로의차이 인 경우이다.

2. 탐색할수 있는 모든 경우에 대해 탐색하여 카운팅 해준다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, res;
int map[15];
 
bool isPromising(int r,int c) {
    for (int i = 1; i < r; i++) {
        // 세로상에 놓여있는지
        if (map[i] == c) return false;
        // 대각선상에 놓여있는지
        if (abs(r - i) == abs(map[i] - c)) return false;
    }
    return true;
}
 
//디버깅용
void printBoard() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (map[i] == j) printf("o ");
            else printf("x ");
        }
        printf("\n");
    }
    printf("\n");
}
 
void dfs(int r, int c) {
 
    map[r] = c;
    if (r == n) {
        //printBoard();
        res++;
    }
    else {
        for (int i = 1; i <= n; i++) {
            if(isPromising(r + 1, i)) {
                dfs(r + 1, i);
            }
        }
    }
    map[r] = 0;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        dfs(1, i);
    }
    printf("%d\n", res);
}