[백준] 9663번: N-Queen

9663번: N-Queen

학교 과제로 풀게 된 N-Queen 문제입니다.

N-Queen 문제는 전형적인 백트래킹 문제라고 할 수 있습니다.

N개의 Queen이 서로 공격할 수 없도록 N * N 체스판에 배치해야 하고, 각각의 Queen들은 가로, 세로, 대각선 방향으로 공격할 수 있으므로 이 방향들을 모두 검사해줘야 합니다.

처음 이 문제를 접했을 때는 이차원 배열을 생각했었는데, 이런 문제들은 중복이 되지 않기만 하면 되므로 이차원 배열 위에서 체크해 줄 필요가 없다고 생각했습니다.

그 자리가 유망한 지를 column 배열을 이용해 검사하고, 각 col에 어떤 row에 있었는지 정보를 저장하는 방식으로 문제를 해결했습니다. (col[i] 의 value가 Queen이 위치한 row)

 

이런 방식을 사용한다면 대각선에 Queen이 있는지 판별하는 것도 수월합니다. |col[i] - col[k]| 이 |i - k|와 일치하는지만 확인해주면 되기 때문입니다.

---

 

새로운 col에 Queen들을 배치하면서 계속해서 이전 col들과 가능한 row의 위치들을 check 해주어야 하는데 얼마 차이는 안 나지만 조금 효율적이었으면 해서 일반적인 N-Queen 문제 해결 방법에 isVisited라는 배열을 추가했습니다.

column만을 활용해 위치를 검사했는데, 이 배열을 추가함으로 이전에 지금 검사하고자 하는 row가 사용된 적이 있는지를 검사했습니다.

 

#include <iostream>
using namespace std;	

int N;
int col[16];
bool isVisited[16];
int ans = 0;

void input() {
  cin >> N;
}

bool isPromising(int i) {
  for (int k = 1; k < i; k++) {
    if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k)) {
      return false;
    }
  }
  return true;
}

void nQueen(int i) {
  if (i > N) { 
    ans += 1;
    return; 
  }
  
  for (int j = 1; j <= N; j++) {
    if (!isVisited[j]) {
      col[i] = j;
      isVisited[j] = true;
      if (isPromising(i)) {
        nQueen(i + 1);
      }
      isVisited[j] = false;
    }
  }
}

void printAnswer() {
  cout << ans << '\n';
}

int main() {
  input();
  nQueen(1);
  printAnswer();
  
  return 0;
}