[백준 9663]N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

평소에 푸는 방법과 다른 풀이방법을 알아냈다.

각 row당 queen은 한개만 존재해야하므로 row는 무조건 1씩 증가한다.

col과 왼쪽 오른쪽 대각선을 고려해주는데

왼쪽 대각선을 보면 각 대각선의 row + col 좌표 합이 일정함을 알 수 있다. 오른쪽 대각선은 row-col이 일정함

이 때 row-col은 음수이므로 offset처리를 해줘야 해서 n-1을 더해준다.

 

// 대각선을 사용하자
#include <stdio.h>

using namespace std;

int answer;
int n;
bool col[15];
bool left[30];
bool right[30];
void dfs(int x, int y)
{
  //만약 이미 있다면 return
  if (col[y] || left[x + y] || right[x - y + n - 1])
  {
    return;
  }

  if (x == n - 1)
  {
    answer++;
    return;
  }

  col[y] = 1;
  left[x + y] = 1;
  right[x - y + n - 1] = 1;
  for (int i = 0; i < n; i++)
  {
    dfs(x + 1, i);
  }
  col[y] = 0;
  left[x + y] = 0;
  right[x - y + n - 1] = 0;
}

int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    dfs(0, i);
  }
  printf("%d\n", answer);
  return 0;
}