[9663] N-Queen

• 입력: 정수 N (1≤N<15)
• 출력: N*N 체스판에 N개의 퀸을 놓을 수 있는 경우의 수
• 알고리즘: 백트래킹
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; void CountQueen(const int, int, int&); vector<int> queen; int main() { int n; scanf("%d", &n); int cnt = 0; for (int i = 0; i < n; i++) { queen.push_back(i); CountQueen(n, 1, cnt); queen.pop_back(); } if (n == 1) printf("1\n"); else printf("%d\n", cnt); return 0; } void CountQueen(const int n, int row, int& cnt) { if (row >= n) return; vector<bool> visit(n, false); for (int i = 0; i < row; i++) { int y = queen[i]; visit[y] = true; if (y + (row - i) < n) visit[y + (row - i)] = true; if (y - (row - i) >= 0) visit[y - (row - i)] = true; } for (int i = 0; i < n; i++) { if (row == n - 1 && !visit[i]) cnt++; else if(!visit[i]){ queen.push_back(i); CountQueen(n, row + 1, cnt); queen.pop_back(); } } }

퀸은 가로, 세로, 대각선으로 칸 제한없이 이동이 가능하다. 서로 잡을 수 없는 상태여야 하므로, 각 줄에 하나의 퀸만 있어야 한다. 그래서 각 열별로 확인을 했다. 우선 (0,0)부터 시작을 한다. 그 때 세로(y)값을 저장해두고, 다음 줄에 퀸을 두기 앞서 놓으면 안될 곳을 표시한다. 그래서 가장 맨 아래줄에 비어있는 칸을 세면 된다. 

• 문제 출저: https://www.acmicpc.net/problem/9663