[C++] 백준 9663 : N-Queen

#include <iostream>

int N, cnt = 0;
int col[15]; // col의 index가 열, col의 값이 행
bool promising(int x){
  for(int i = 0; i < x; i++){
    // 세로나 대각선에 위치하는 경우 - 가로는 이미 반복문을 사용해 한 행에 하나만 위치하도록 제한하여 상관 x
    if(col[i] == col[x] || abs(col[i] - col[x]) == x - i){
      return false; // 퀸 놓기 불가능
    }
  }
  return true; // 유망함 - 퀸 놓기 가능
}

void nQueens(int x){
  if(x == N){ // 마지막 줄에 퀸을 둘 수 있는 경우
    cnt++;
  } else {
    for(int i = 0; i < N; i++){ // 모든 열 체크하면서
      col[x] = i; // 퀸 배치
      if(promising(x)){ // 유효한 경우
        nQueens(x+1); // 다음 행에 퀸 배치
      }
    }
  }
}
int main(){
  scanf("%d", &N);
  nQueens(0); // 제일 처음 행부터 퀸 두기 시작
  printf("%d", cnt);
  return 0;
}

백트래킹 연습용으로 푼 문제.
백트래킹은 DFS를 생각하면 좋다. DFS는 스택이랑 재귀로 구현할 수 있는데 여기서는 재귀함수를 이용해서 풀었다.

가로 세로 대각선이 모두 겹치면 안된다.

1. 가로 : 반복문을 사용하여 col 당 퀸을 무조건 1개만 둘 수 있도록 지정하였다.
2. 세로, 대각선 : promising 함수의 조건문을 제시하여 제한을 두었다.

생각하는 것과 코드를 보면 해석하는 것은 참 쉬운데 왜 생각한 것을 코드로 풀어내는 것은 이렇게 어려운 것인지 잘 모르겠다. 더 연습해봐야지.