[백준 9663] N-Queen을 여러가지 방법으로 풀어보자!

1. Naive한 구현(TLE)

이 문제를 푸는 가장 간단한 구현은 2차원 체스판을 그대로 가지고 와서 백트래킹을 해주면 된다.

가장 평범하게 문제를 해결하는 방법이다.

 

1행 1열부터 퀸을 배치할 수 있는지 확인하고 불가능하면 다음 칸으로 넘어가는 식으로 해주면 된다.

퀸을 배치한 곳은 1로 표시한다.

 

배치하고 싶은 곳을 check함수를 통해 이전 배치한 퀸들과의 마주봄이 있는지를 확인했다.

row를 재귀로써 탐색하므로 각 row에는 1개의 퀸만이 올 수 있기 때문에 check함수에서 row는 검사할 필요가 없다.

 

#include <iostream>
using namespace std;

int n, board[16][16], ans;

bool check(int x, int y){
  for(int i = 1; i < x; i++){
    if(board[i][y]) return false;
    if((x-i >= 0) && (y-i >= 0)){
      if(board[x-i][y-i]) return false;
    }
    if((x-i >= 0) && (y+i) <= n){
      if(board[x-i][y+i]) return false;
    }
  }
  return true;
}

int trial(int cur){
  if(cur == n){
    ans++;
    return 0;
  }
  int tmp[16][16];
  for(int col = 1; col <= n; col++){
    if(check(cur+1,col)){
      board[cur+1][col]=1;
      trial(cur+1);
      board[cur+1][col]=0;
    }
  }
  return ans;
}

int main(){
  cin >> n;
  cout << trial(0);
}

 

2. 1차원으로 구현(AC)

1번 코드(나이브하게 구현한 코드)의 단점은 check함수에서 실제 다른 퀸이 있는 곳까지 직접 이동하며 확인한다는 것이다.

이것을 for문을 사용하여 구현하였는데 잘 생각해보면 for문이 필요하지 않다.

 

퀸은 체스 규칙상 퀸이 놓여진 모든 행, 열, 대각선을 커버하기 때문에 굳이 퀸이 있는 곳까지 직접 이동하여 확인할 필요 없이 해당 열에, 해당 대각선상에 퀸이 있는지를 확인하기만 하면 된다.

 

한마디로 퀸이 존재한다는 것을 직접 2차원 체스판에 표시하지 않고 

col: 퀸이 있는 열을 표시할 배열 (어차피 한 열에 한개의 퀸 밖에 오지 않으므로 1차원 배열로 표시해도 됨)

dia1: 배치할 퀸을 중심으로 우상향 대각선에 퀸이 있는지 확인할 배열 (우상향 대각선은 row+col = 일정 하다는 특징이 있음)

dia2: 배치할 퀸을 중심으로 좌상향 대각선에 퀸이 있는지 확인할 배열 (좌상향 대각선은 row-col = 일정 하다는 특징이 있음)

 

예를 들어

col[16] 배열에서 col[1] = 1이면 이미 이전 과정에서 퀸이 1열에 배치된 것이므로 1열에는 퀸 배치가 불가능함.

(대각선의 배열 크기가 31인 이유는 n의 제한이 15인데 각 row+col의 값이 15+15=30까지 등장할 수 있으므로)

dia1[31] 배열에서 dia1[5] = 1이면 row+col = 5인 대각선상에 이미 퀸이 배치된 것이므로 해당 칸에 퀸 배치가 불가능함.

dia2[31] 배열에서 dia2[6] = 1이면 row-col+n=6인 대각선상에 이미 퀸이 배치된 것이므로 해당 칸에 퀸 배치가 불가능함.

*dia2배열에서 n을 더해주는 이유는 row-col의 값이 음수가 나오면 배열에 표시할 수 없으므로 적당한 값을 더해서 양수로 만들어서 관리 (만약 100과 같은 정수를 더해도 되지만 그러면 배열의 크기가 더 커져야하고 공간만 차지하는 배열이 생김)

 

다음과 같이 1차원 배열로 하면 check부분에서 O(n)의 for문이 필요하지 않기 때문에 시간복잡도가 크게 낮아진다.
(지수적으로 실행되기 때문에 각 시행에 for문이 하나만 없어도 시간복잡도도 지수적으로 이득을 볼 수 있다)

#include <iostream>
using namespace std;

int n, ans, col[16], dia1[31], dia2[31];

bool check(int r, int c){
  if(col[c] || dia1[r+c] || dia2[r-c+n] ) return false;
  return true;
}

int trial(int cur){
  if(cur == n+1) {
    return ans++;
  }
  for(int c = 1; c <= n; c++){
    if(check(cur, c)){
      col[c] = dia1[cur+c] = dia2[cur-c+n] = 1;
      trial(cur+1);
      col[c] = dia1[cur+c] = dia2[cur-c+n] = 0;
    }
  }
  return ans;
}

int main(){
  cin >> n;
  cout << trial(1);
}

 

3. 비트마스킹(AC)

비트마스킹을 활용하면 시간을 더 줄일 수 있는데

비트 자체에 퀸의 정보를 넣는 것이다.

따라서 2번에서의 col, dia1, dia2와 같은 배열도 필요없고 정보를 담는 변수로 모두 처리 가능하다.

 

예를 들어서

col = 0001 이라면 가장 오른쪽 비트를 1열로 생각하고 1열에 퀸이 놓여져 있다고 생각할 수 있다.

 

대각선 비트는 ld(좌하향), rd(우하향)으로 관리하는데 퀸을 놓음으로 인해 다음 열에 오지못하는 공간만 비트로 표시한다.

예를들어 (3,4)에 퀸을 놓았다면 ld로 인해 다음행의 3번째 열에는 퀸을 놓지 못한다. 비트로는 ld = 0100 으로 표시할 수 있다.

rd는 ld와 반대로 다음 행의 5번째 열에는 퀸을 놓지 못한다. 비트로는 rd = 10000 으로 표시할 수 있다.

 

정리하면 대각선 변수는 다음 행의 몇번째 열이 이전 퀸들의 영향을 받고 있는지를 나타낸 것이다.

또 다음 재귀(다음 행)으로 넘어갈 때 col, ld, rd의 정보들의 합이 퀸이 배치될 수 없는 칸인 것이다.

반대로 말하면 col, ld, rd 정보들의 여집합은 해당 행에서 퀸이 배치될 수 있는 열이 되는 것이다.

 

#include <iostream>
using namespace std;

int n, ans;
//ld: 좌상향, rd: 우상향
void trial(int row, int col, int ld, int rd){
  if(row == (1 << n) - 1){
    ans++;
    return;
  }

  //Queen이 가능한 곳이 1
  int avail = ~(col | ld | rd) & ((1 << n) - 1);

  while(avail){
    int bit = avail & -avail;
    avail ^= bit;
    //퀸을 놓으면 1
    trial(row|bit, col|bit, (ld | bit) >> 1, (rd | bit) << 1);
  }
}

int main(){
  cin >> n;
  trial(0,0,0,0);
  cout << ans;
}