[백준] 9663번 N-Queen - C/C++

백준 9663문제(Problem)

백준 9663 문제

 

풀이(Solution)

이 문제를 풀기 전에 퀸이 움직일 수 있는 방향을 알아야 한다. 필자는 체스를 안한지 오래되어 찾아보았다.

퀸이 움직일 수 있는 방향은 아래 그림과 같다.(대각선 네 방향 + 상하좌우)

퀸이 움직일 수 있는 방향

하지만 우리는 퀸보다 위에 있는 방향만 체크할 것이다. 왜냐면 백트래킹을 사용할 것이기 때문이다.

 

필자가 사용한 함수는 다음과 같다.

- setting 함수: 퀸을 놓는 함수

- check 함수: 현재 위치에 퀸을 놓을 수 있는지 확인하는 함수

 

<setting 함수> (매개변수 depth: y값이라고 생각해도 무방하다)

먼저, 퀸을 (0,0)자리에 놓을 수 있는지 check 함수를 통해 확인한다. 가능하다면 놓고, setting(depth+1)로 재귀 호출을 해준다.

여기에서 depth+1을 하는 이유는 어차피 현위치에서의 좌우 방향에는 퀸을 놓지 못하기 때문에 다음 아래 방향으로 가야한다.

이러한 방식으로 재귀호출을 하고 가장 아래까지 놓았을 때, cnt를 증가시킨다.

 

<check 함수> (매개변수 x, y)

필자는 3개의 while문을 통해 퀸을 놓을 수 있는지 확인하였다. 놓을 수 없으면 0을 반환, 있으면 1을 반환한다.

첫번째 while문은 대각선 왼쪽위 방향을 탐색한다.

두번째 while문은 대각선 오른쪽 위 방향을 탐색한다.

세번째 while문은 위쪽 방향을 탐색한다.

 

여기서 퀸의 아래방향을 탐색하지 않는 이유가 궁금한 분들도 있을 것이다. 백트래킹 기법을 사용하니, 아직 아래쪽에는 퀸을 놓지 않은 상태이기 때문에 놓지 않는다.

 

코드(Code)

#include<iostream>
using namespace std;
int N, a[16][16], nx, ny, cnt;

// 퀸을 놓을 수 있는지 확인하는 함수
// 놓을 수 있으면 1, 없으면 0 반환
bool check(int y, int x) {
  nx=x, ny=y;
  while(nx-- && ny--)
    if(a[ny][nx]) return 0;

  nx=x, ny=y;
  while(nx++<N && ny--)
    if(a[ny][nx]) return 0;

  nx=x, ny=y;
  while(ny--)
    if(a[ny][nx]) return 0;

  return 1;
}

// 퀸을 놓는 함수
void setting(int depth) {
  if(depth == N) { cnt++; return; }
  for(int i=0; i<N; i++) {
    if(check(depth, i)) {
      a[depth][i]=1;
      setting(depth+1);
      a[depth][i]=0;
    }
  }
}

int main() {
  cin >> N;
  setting(0);
  cout << cnt;
}