[Java] 백준 9663번 N-Queen

브루트포스 문제입니다.

퀸을 서로가 공격 할 수 없게 놓을 수 있는 경우의 수를 구해야 합니다.

퀸은 직선과 대각선에 있으면 공격할 수 있으므로
퀸의 직선과 대각선에 다른 퀸이 존재하지 않게 두어야합니다.

비트를 사용해서 아래와 같이 처리했습니다.
1은 왼쪽 대각선
2는 직선
4는 오른쪽 대각선

비트 값을 확인하여 다음 줄에 놓을 수 있는지 체크합니다.

체크가 안 된 위치에 퀸을 두고 다음 줄을 확인합니다.

위의 과정을 반복하여 마지막 줄까지 퀸을 둘 수 있는 경우를 카운팅해서 출력해 주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  static int n;
  static int[][] arr;
  static int result;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    n = Integer.parseInt(br.readLine());
    result = 0;

    if (n == 1) {
      bw.write("1\n");
    } else {
      for (int i = 1; i <= n; ++i) {
        arr = new int[n + 1][n + 1];
        arr[1][i] = 7;
        dfs(2);
      }
      bw.write(result + "\n");
    }

    bw.close();
  }

  public static void dfs(int cnt) {
    for (int i = 1; i <= n; ++i) {
      if ((arr[cnt - 1][i] & 1) != 0 && i > 1) {
        arr[cnt][i - 1] = (1 | arr[cnt][i - 1]);
      }
      if ((arr[cnt - 1][i] & 2) != 0) {
        arr[cnt][i] = (2 | arr[cnt][i]);
      }
      if ((arr[cnt - 1][i] & 4) != 0 && i < n) {
        arr[cnt][i + 1] = (4 | arr[cnt][i + 1]);
      }
    }

    for (int i = 1; i <= n; ++i) {
      if (arr[cnt][i] == 0) {
        if (cnt == n) {
          ++result;
          continue;
        }
        arr[cnt][i] = 7;
        dfs(cnt + 1);
        arr[cnt][i] = 0;
      }
    }

    for (int i = 1; i <= n; ++i) {
      arr[cnt][i] = 0;
    }
  }
}