[BOJ] 9663 - N-Queen

https://www.acmicpc.net/problem/9663

BOJ - N-Queen

문제 유형: 완전 탐색, dfs, 백트래킹, 재귀

문제 난이도: Gold IV

시간 제한: 10초

메모리 제한: 128MB

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

풀이

재귀 함수 solve(row)에는 이제 퀸을 넣어야 할 행의 인덱스 row를 받는다.

첫 번째 방법은, 직접 N * N의 보드를 만들어서 직접 퀸이 공격하는 영역에 표시를 해두고, 공격받지 않는 열에 퀸을 두고 재귀호출한 뒤, 호출이후에 퀸을 다시 회수하는 방법이 있다.

 

두 번째 방법은, 직접 2D배열에 위협칸을 만드는 것이 아닌, 해당 열 및 대각선에 위협을 받고 있는지만 저장하는 것이다.

열과 두 가지 대각선에 모두 위협받고 있지 않다면, 그 열에 놓을 수 있는 것이다. 그리고 위협 정보를 넣어두고, 재귀호출한 뒤, 다시 회수한다는 개념으로 위협을 빼주면 된다.

 

코드

C++

 

직접 보드에 위협을 추가하는 버전

#include <bits/stdc++.h>

using namespace std;

int n;

void putOnBoard(int r, int c, vector<vector<int>> &board) {
  for (int i = 0; i < n; ++i) {
    board[r][i]++;
    board[i][c]++;
  }
  for (int i = 1; r + i < n && c - i >= 0; ++i) {
    board[r + i][c - i]++;
  }
  for (int i = 1; r - i >= 0 && c + i < n; ++i) {
    board[r - i][c + i]++;
  }
  for (int i = 1; r - i >= 0 && c - i >= 0; ++i) {
    board[r - i][c - i]++;
  }
  for (int i = 1; r + i < n && c + i < n; ++i) {
    board[r + i][c + i]++;
  }

  board[r][c]--;
}

void removeFromBoard(int r, int c, vector<vector<int>> &board) {
  for (int i = 0; i < n; ++i) {
    board[r][i]--;
    board[i][c]--;
  }
  for (int i = 1; r + i < n && c - i >= 0; ++i) {
    board[r + i][c - i]--;
  }
  for (int i = 1; r - i >= 0 && c + i < n; ++i) {
    board[r - i][c + i]--;
  }
  for (int i = 1; r - i >= 0 && c - i >= 0; ++i) {
    board[r - i][c - i]--;
  }
  for (int i = 1; r + i < n && c + i < n; ++i) {
    board[r + i][c + i]--;
  }

  board[r][c]++;
}

int solve(int row, vector<vector<int>> &board) {
  if (row >= n) {
    return 1;
  }
  int res = 0;
  for (int i = 0; i < n; ++i) {
    if (board[row][i] == 0) {
      putOnBoard(row, i, board);
      res += solve(row + 1, board);
      removeFromBoard(row, i, board);
    }
  }
  return res;
}

int main(int argc, char *argv[]) {
  cin >> n;
  if (n == 1) {
    cout << "1\n";
    return 0;
  }
  vector<vector<int>> board(n, vector<int>(n, 0));

  cout << solve(0, board) << "\n";

  return 0;
}

 

최적화된 버전 - 열, 대각선의 위협 정보를 저장해서 1차원배열로 해결하기

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> cols, primaryDiag,
    secondaryDiag; // primaryDiag: topleft -> bottomright // secondaryDiag:
                   // bottomleft -> topright

int solve(int row) {
  if (row >= n)
    return 1;
  int res = 0;
  for (int col = 0; col < n; ++col) {
    if (cols[col] || primaryDiag[row + col] || secondaryDiag[row - col + n - 1])
      continue;

    cols[col]++;
    primaryDiag[row + col]++;
    secondaryDiag[row - col + n - 1]++;
    res += solve(row + 1);
    cols[col]--;
    primaryDiag[row + col]--;
    secondaryDiag[row - col + n - 1]--;
  }
  return res;
}

int main(int argc, char *argv[]) {
  cin >> n;
  cols.resize(n, 0);
  primaryDiag.resize(2 * n - 1, 0);
  secondaryDiag.resize(2 * n - 1, 0);
  cout << solve(0) << "\n";
  return 0;
}