Difference between r1.2 and the current
@@ -8,7 +8,45 @@
= 코드 =
== 15이원준 ==
{{{
#include<iostream>
using namespace std;
int N = 0;
int ans = 0;
void putQueen(int dep, int loca[15], int visit){
if(dep == -1){
ans++;
return;
}
for(int i = 0; i < N; i++){
if(!(visit & 1 << i)){
bool checker = true;
for(int k = dep + 1; k<N; k++){
if(loca[k] == i + k - dep || loca[k] == i - k + dep){
checker = false;
break;
}
}
if(checker){
loca[dep] = i;
putQueen(dep-1, loca, visit + (1 << i));
}
loca[dep] = 0;
}
}
}
int main(){
cin>> N;
int loca[15] = { 0, };
putQueen(N-1,loca, 0);
cout<<ans<<endl;
}
}}}
== 박인서 =={{{
#include <iostream>
@@ -67,7 +105,12 @@
= 아이디어 =
== 15이원준 ==
* 대각선에 있지 않으려면 같은 컬럼이나 로우에는 두어서는 안됩니다.
* 따라서 loca[i] = j는 판의 i,j에 놓는다는 의미로 사용하여 한 컬럼 혹은 로우에는 하나씩만 두는 것을 보장합니다.
* dep에 따라 dep번째 컬럼 혹은 dep번째 로우에 몇번째 칸에 둘지를 결정합니다.
* 각 dep에서는 현재 까지 둔 것과 자신이 둘 곳을 비교하여 둘수있는지 확인합니다.
* int형 visit을 이용하여 i번째 비트를 그 컬럼 혹은 로우를 사용했는지 체크합니다.
* dep가 -1일때, 즉 말을 서로 잡을 수 없는 곳에 N개를 놓았을 경우입니다.
== 박인서 ==* Queen은 자신의 상하좌우에 모두 다른 말이 있으면 잡힌다.
* 따라서 1줄씩 Queen을 놓고 상하좌우를 체크한다.
3.1. 15이원준 ¶
#include<iostream>
using namespace std;
int N = 0;
int ans = 0;
void putQueen(int dep, int loca[15], int visit){
if(dep == -1){
ans++;
return;
}
for(int i = 0; i < N; i++){
if(!(visit & 1 << i)){
bool checker = true;
for(int k = dep + 1; k<N; k++){
if(loca[k] == i + k - dep || loca[k] == i - k + dep){
checker = false;
break;
}
}
if(checker){
loca[dep] = i;
putQueen(dep-1, loca, visit + (1 << i));
}
loca[dep] = 0;
}
}
}
int main(){
cin>> N;
int loca[15] = { 0, };
putQueen(N-1,loca, 0);
cout<<ans<<endl;
}
3.2. 박인서 ¶
#include <iostream>
#include <vector>
bool a[16][16]={false,};
int cnt=0,n;
bool check(int row,int col)
{
for(int i=0;i<col;i++)
if(a[row][i]) return false;
for(int i=0;i<n;i++)
if(a[i][col]) return false;
for(int i=1;;i++)
{
if(row-i<0 || col-i<0) break;
if(a[row-i][col-i]) return false;
}
for(int i=1;;i++)
{
if(row-i<0 || col+i>=n) break;
if(a[row-i][col+i]) return false;
}
return true;
}
void queen(int row)
{
if(row==n)
{
cnt++;
return;
}
for(int i=0;i<n;i++)
{
if(check(row,i))
{
a[row][i]=true;
queen(row+1);
a[row][i]=false;
}
}
}
int main()
{
std::cin>>n;
queen(0);
std::cout<<cnt;
return 0;
}
4.1. 15이원준 ¶
- 대각선에 있지 않으려면 같은 컬럼이나 로우에는 두어서는 안됩니다.
- 따라서 locai = j는 판의 i,j에 놓는다는 의미로 사용하여 한 컬럼 혹은 로우에는 하나씩만 두는 것을 보장합니다.
- dep에 따라 dep번째 컬럼 혹은 dep번째 로우에 몇번째 칸에 둘지를 결정합니다.
- 각 dep에서는 현재 까지 둔 것과 자신이 둘 곳을 비교하여 둘수있는지 확인합니다.
- int형 visit을 이용하여 i번째 비트를 그 컬럼 혹은 로우를 사용했는지 체크합니다.
- dep가 -1일때, 즉 말을 서로 잡을 수 없는 곳에 N개를 놓았을 경우입니다.
