1R/2016 09 21

오늘의 문제

• [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;
}

박인서

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

아이디어

박인서

• Queen은 자신의 상하좌우에 모두 다른 말이 있으면 잡힌다.
• 따라서 1줄씩 Queen을 놓고 상하좌우를 체크한다.
• 이 것을 이용하는데 전체적으로 Queen 탐색이 왼쪽 위에서 시작되므로 4개 방향만 탐색을 해주면 된다.