문제
풀이
Reference : Here
NxN 체스판 위에 N개의 퀸을 놓는 경우의 수를 구하는 문제로, 백트래킹 문제이다. Col[y] = x 는 (x, y)를 의미하며, 맨 왼쪽 열 0부터 맨 오른쪽 열 N까지 퀸을 놓고 check 함수로 동선이 겹치는 부분을 거르며 백트래킹으로 구현한 문제이다. 대각선에 위치한 동선을 거르는 방법은 x좌표와 y좌표의 차이가 일정한 곳을 거르는 방법으로 진행되었다.
소스 코드
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
#include <iostream>
using namespace std;
int N;
int cnt;
int col[15];
bool check(int level)
{
for(int i = 0; i < level; i++)
if(col[i] == col[level] || abs(col[level] - col[i]) == level - i) // x좌표가 같은 곳을 거르는 것과, 왼쪽에 위치한 대각선들을 거르는 코드
return false;
return true;
}
void Queen(int a){
if(a == N){
cnt++;
}
for(int i = 0; i<N; i++){
col[a] = i;
if(check(a)){
Queen(a+1); //
}
}
}
int main(){
scanf("%d", &N);
Queen(0);
printf("%d\n", cnt);
}
