BOJ_9663 - N-Queue (JAVA)

문제

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

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

풀이

퀸은 위, 아래, 왼쪽, 오른쪽, 대각선으로 이동가능하다.
즉 (x,y)에 퀸이 놓인다면 같은 열과 행에는 퀸이 올 수 없다.
위와 같이 위, 아래, 왼쪽, 오른쪽은 같은 열인지 행인지 확인만 해주면 되므로 어렵지 않다. 문제는 대각선이다.
답을 먼저 설명하자면 x가 증가하는 방향의 대각선은 x-y가 같으면 퀸이 올 수 없고, x가 감소하는 방향의 대각선은 x+y가 같을때 퀸이 올 수 없다.
기울기를 구할떄 y증가량 / x증가량 을 이용한다는 것을 안다면 알 수 있는 사실이다.

재귀함수는 어떻게 구성해야 할까? 먼저 퀸의 갯수가 N일때 카운트가 증가해야한다. 이를 코드로 나타내면 다음과 같다

public static void dfs(int depth) {
	if(depth == N) {
    	cnt++;
        return
    }
}

여기서 depth는 행을 뜻한다. 하나의 행에는 한개의 퀸만 존재할 수 있기 때문이다. 그래서 퀸의 갯수가 N이 되기위해서는 행마다 하나의 퀸이 존재해야한다.

이제 열과 대각선에 위협하 퀸이 있는지 확인후에 없다는게 확인되면 재귀호출해준다.

열과 대각선에 위협을 할 수 있는 퀸이 존재하는지 체크해주기 위해 3개의 boolean배열을 만들어 주었다.

static boolean[] isUsed1 = new boolean[40];
static boolean[] isUsed2 = new boolean[40];
static boolean[] isUsed3 = new boolean[40];

isUsed1은 같은 열에 퀸이 있는지 체크해주는 역할이다.
즉 현재 열이 i라면 isUsed1은[i]를 통해 체크 가능하다.
isUsed2,isUsed3은 대각선에 위협하는 퀸이 있는지 체크해주는 역할이다.
즉 isUsed2[depth+i],isUsed3[depth-i+N-1]로 체크 가능하다.
depth-i이 아닌 depth-i+N-1을 해주는 depth-i가 음수가 되는 경우가 있을 수 있기 때문이다.

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
  static int N;
  static int cnt = 0;
  static boolean[] isUsed1 = new boolean[40];
  static boolean[] isUsed2 = new boolean[40];
  static boolean[] isUsed3 = new boolean[40];
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    
    dfs(0);
    System.out.println(cnt);
  }
  public static void dfs(int depth) {
    if(depth == N) {
      cnt++;
      return;
    }   
    for(int i=0; i<N; i++) {
      if(isUsed1[i] || isUsed2[depth+i] || isUsed3[depth-i+N-1]) continue;
      isUsed1[i] = true;
      isUsed2[depth+i] = true;
      isUsed3[depth-i+N-1] = true;
      dfs(depth+1);
      isUsed1[i] = false;
      isUsed2[depth+i] = false;
      isUsed3[depth-i+N-1] = false;
    }
  }
 
}