백준 9663 자바 n-queens문제

백준 9663 N-Queen

문제

• 백트랙킹으로 유명한 n-queen문제이다.

• 간략하게 문제는 이렇다.

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

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

  

  위 그림은 체스를 놓을 수 있는 방법중 하나이다. 체스의 퀸은 양 옆, 아래 ,대각선을 공격할 수 있기 때문에 조건으로 양 옆,아래,대각선 이렇게 있으면 안된다. 처음에 과연 어떻게 체스의 위치를 알 수 있을까 생각을 하다가 좌표를 그려보았다. 그리고 각 행에 한 개의 체스만 놓을 수 있다는 것을 알게 되었다.

  그러면 각 행에 체스 퀸을 놓고 DFS형식으로 문제를 풀면 되겠다고 생각을 하였고 체스 퀸을 하나 놓을 때 마다 위치의 조건식을 체크 해주면 되겠다. 즉, 첫 번째 체스를 놓을 때는 체스 판에서 자신밖에 없으니 조건식을 안해도 되고 두 번째 행에 체스를 놓을 때 부터 조건식을 타게끔 만들어 주면 되겠다.

  코드는 다음과 같다.

  • 중요한 포인트는 대각선을 어떻게 비교하냐는 건데 좌표를 보면 서로 대각선 상에 있을 때 각 대각선에 있는 좌표를 x좌표는 x좌표끼리 y좌표는 y좌표끼리 빼서 절댓값으로 변환한 다음 같으면 대각선상에 있는 것이다.

  private static boolean check(int row, int y) {
          //열이랑 대각선을 확인해주면 되지않을까..??
          for (int i=0; i<row; i++) {//여기서 첫번째 행은 즉 row가 0행 (실제로는 1행) 일 떄는 비교할 것이 없으니깐 안돌아도 무방!!!
              if (node[i] == y || Math.abs(row-i) == Math.abs(y - node[i]))
                  return false;
          }
          return true;
      }

  그리고 또한 반복문으로 반복을 하면서 row를 증가 시켜주기 때문에 굳이 2차원 배열을 생성할 필요는 없다. 코드는 아래와 같다.

  private static void dfs(int row) {
          if (row == N) {//x가 4이면 4행 즉, 끝까지 왔다는 증거이니깐 count를 +1해주고 return을 해줘야한다.
              count++;
              return;
          }
          for (int y=0; y<N; y++) {
              if (check(row,y)) {
                  node[row] = y;//값으로는 열(col)의 정보를 준다.
                  dfs(row + 1);
              }
          }
      }

  이처럼 dfs코드를 호출 할 때 row를 매개변수로 같이 보내주기 때문에 2차원 배열을 안해도 무방하다.

• 그럼 전체적인 코드를 보겠다.

  package twoweekpractice;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class Q9663 {
      public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      public static int count = 0;
      public static int node[];
      public static int N;
      public static void main(String[] args) throws IOException {
          N = Integer.parseInt(br.readLine());
          node = new int[N];
          dfs(0);
          System.out.println(count);
      }
  
      private static void dfs(int row) {
          if (row == N) {//x가 4이면 4행 즉, 끝까지 왔다는 증거이니깐 count를 +1해주고 return을 해줘야한다.
              count++;
              return;
          }
          for (int y=0; y<N; y++) {
              if (check(row,y)) {
                  node[row] = y;//값으로는 열(col)의 정보를 준다.
                  dfs(row + 1);
              }
          }
      }
  
      private static boolean check(int row, int y) {
          //열이랑 대각선을 확인해주면 되지않을까..??
          for (int i=0; i<row; i++) {//여기서 첫번째 행은 즉 row가 0행 (실제로는 1행) 일 떄는 비교할 것이 없으니깐 안돌아도 무방!!!
              if (node[i] == y || Math.abs(row-i) == Math.abs(y - node[i]))
                  return false;
          }
          return true;
      }
  }