baekjoon 9663:N-Queen

baekjoon 9663 N-Queen

9663번 N-Queen

접근

backtracking으로 푸는 문제이다.
n*n판에 n개가 들어가야 하니 1row에 1개 들어가야한다.
위에서부터 하나씩 채워나가는 걸 depth로 생각하면 된다. check함수가 둘 수 있는 곳인지 확인해준다.

코드

#include <iostream>
#include <vector>
using namespace std;
int backtracking(vector<pair<int, int>>& g);
bool check(vector<pair<int, int>>& g);
int n;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  vector<pair<int, int>> g;
  cout << backtracking(g);
  
}
int backtracking(vector<pair<int, int>>& g){
  int ret = 0;
  if(g.size() == n){
    return 1; //끝 도달
  }
  for(int i = 0; i < n; i++){
    g.push_back({g.size()+1, i+1});
    if(check(g)){
      ret += backtracking(g);
    }
    g.pop_back();
  }
  return ret;
}
bool check(vector<pair<int, int>>& g){
  //전꺼까진 다 확인했으니 새로 둔 것만 확인하면 된다
  for(int i = 0; i < g.size()-1; i++){
    if(g[i].first == g[g.size()-1].first || g[i].second == g[g.size()-1].second || g[i].first - g[g.size()-1].first == g[i].second - g[g.size()-1].second || g[i].first - g[g.size()-1].first == g[g.size()-1].second - g[i].second){
      return false;
    }
  }
  return true;
}

배운 점

넣고 안넣고 정도의 2가지 경우만 있는 백트레킹에서 여러 갈래가 있는 벡트레킹까지 해보았다.