[Programmers] N-Queen

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

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

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

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

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

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

 

 

#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; }