[프로그래머스/C++] N-Queen - 컴도리돌이

문제 설명

• 가로, 세로 길이가 n인 정사각형으로 된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
• 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한 번에 공격할 수 없습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return 하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수입니다.

<코드>

#include <string> #include <vector> using namespace std; int board_size ; int answer = 0; bool is_possible(int h, int w,vector<vector<bool>>& board){ for(int i =0; i< h; i++){ if(board[i][w] == true) return false; } int temp_h = h - 1; int temp_w = w - 1; while(temp_h >= 0 and temp_w >= 0){ if(board[temp_h][temp_w] == true) return false; temp_h--; temp_w--; } while(h >= 0 and w <= board_size){ if(board[h][w] == true) return false; h--; w++; } return true; } void dfs(int cur,vector<vector<bool>> board){ if(cur == board_size +1){ answer++; return; } for(int i=0; i<=board_size; i++){ if(is_possible(cur,i,board)){ board[cur][i] = true; dfs(cur+1,board); board[cur][i] = false; } } } int solution(int n) { vector<vector<bool>> board(n,vector<bool>(n,false)); board_size = n-1; dfs(0,board); return answer; }

<제일 따봉을 많이 받은 코드..>

#include<algorithm> #include<vector> using namespace std; long long nQueen(int n) { if (n > 26) return -1; long long result[] {1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184, 14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644, 24233937684440, 227514171973736, 2207893435808352, 22317699616364044 }; return result[n]; }