[Programmers] N-Queen

*퀸은 세로, 가로, 대각선에 있는 말을 한 번에 공격할 수 있으므로, 한 줄에 한 개씩만 배치될 수 있다. 

즉, 최대 n개의 말만 배치될 수 있다. (종료조건)

*맨 윗 칸에 퀸을 한 개씩 놓아보면서 dfs를 통해 모든 경우를 살펴본다. 

[0][0] 에 퀸이 놓였으면 이제 각 줄의 [0]번째 칸에는 퀸이 놓일 수 없다. (chk[0] = true를 해서 구별했다)

*check(x, y, n)에서 현재 칸에서 왼쪽 위 대각선, 오른쪽 위 대각선을 살펴보면서 퀸을 놓을 수 있는지 확인한다. 

*놓을 수 있다면 퀸을 놓고, 다음 줄을 본다. (백트래킹)

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include <string> #include <vector>   using namespace std; bool map[12][12]; bool chk[12];  int answer = 0; bool check(int x, int y, int n) {     int nx = x, ny = y;     while(nx-1 >= 0 && ny -1 >= 0) {         if (map[nx-1][ny-1]) return false;         nx--;         ny--;     }     nx = x;     ny = y;     while(nx-1 >= 0 && ny +1 < n) {         if (map[nx-1][ny+1]) return false;         nx--;         ny++;     }     return true; } void dfs(int cnt, int n) {     if (cnt == n) {         answer++;         return;     }           for (int i = 0; i < n; i++) {         if (!chk[i]) {             if (check(cnt, i, n)) {                 chk[i] = true;                 map[cnt][i] = true;                 dfs(cnt+1, n);                 map[cnt][i] = false;                 chk[i] = false;             }         }     } } int solution(int n) {       for (int i =0; i < n; i++) {         map[0][i] = true;         chk[i] = true;         dfs(1, n);         chk[i] = false;         map[0][i] = false;     }     return answer; }