[BOJ][백트래킹][골5]][9663] N-Queen

문제 링크

문제 링크

풀이

알고리즘

N자리 K진수를 적용해서 해결하는 문제입니다.

v[a]=b는 (a,b)에 퀸이 위치함을 의미합니다. 이 때 각 퀸들이 같은 row/col에는 올 수 없기 때문에 visited[]를 사용합니다. 그리고 isPossible()함수는 직접 8방향으로 시뮬레이션을 하느 것이 아니라, 좌표값의 차이를 통해서 서로의 대각선에 위치했는지 판별합니다.

배열을 사용한 정답 코드

#include <bits/stdc++.h>

#define MAX 20
using namespace std;
typedef long long ll;

int n = 0, k = 0; //N:배열의 길이 , K: 진수
int input[MAX];
int v[MAX]; // v[i] = i번째 row의 말 위치
bool visited[MAX];
int ans = 0;

bool check(int depth) {
  // depth-2번째와 depth-1번째가 놓을 수 있는 위치인지 판단
  // depth -1까지 위치가 정해진 상태
  if (depth <= 1) return true;
  
  // 가로가 겹치는 경우 : row마다 하나씩 선택한다는 조건으로 만족
  // 세로가 겹치는 경우 : visited를 사용해서 한 행에서는 하나만 선택하는 조건으로 만족
  // 대각선으로 겹치는 경우

  int x2 = depth - 1;
  int y2 = v[x2];
  for (int i = depth - 2; i >= 0; i--) {
    int x1 = i;
    int y1 = v[x1];
    if (abs(x2 - x1) == abs(y2 - y1)) return false;
  }
  return true;
}

void recur(int depth) {
  if (!check(depth)) return;
  if (depth == n) {
    /*for (int i = 0; i < n; i++) {
      cout << v[i] << " ";
    }
    cout << "\n";*/
    ans++;
    return;
  }

  for (int i = 0; i < n; i++) {
    if (visited[i]) continue;
    v[depth] = i;
    visited[i] = true;
    recur(depth + 1);
    visited[i] = false;
  }
}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  recur(0);
  cout << ans << "\n";
  return 0;
}

Success Notice: N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.