[백준]9663. N-Queen - Java

📄 링크

N-Queen

---

💡 문제 분석

N * N 크기의 체스판 위에 N개의 퀸을 놓아야 하는 문제입니다
1행부터 N행까지 내려가며 행마다 하나의 퀸을 놓는 방식으로 하기로 했습니다
여기서 어떤 열에 퀸을 놓을 지 정할 때 이미 놓은 퀸들과 왼쪽 대각선, 오른쪽 대각선, 세로가 겹치면 안됩니다.
(1, N - 1)에서 오른쪽 대각선 방향으로 가장 밑으로 갔을 때 2 * N - 1 까지 갈 수 있기 때문에 대각선 배열은 2 * N - 1의 크기로 할당해 주었습니다.

---

⌨️ 코드

public class _9663_Nqueen { 
   static int N, ret = 0;
   static boolean[] diag1, diag2, col;

   public static void backtracking(int cnt){
      if(cnt == N) {
         ret++;
         return;
      }
      for(int next = 0; next < N; next++) {
         if(col[next] || diag1[cnt + next] || diag2[cnt + N - 1 - next]) continue;
            col[next] = diag1[cnt + next] = diag2[cnt + N - 1 - next] = true;
            backtracking(cnt + 1);
            col[next] = diag1[cnt + next] = diag2[cnt + N - 1 - next] = false;
      }
   }

   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      N = sc.nextInt();
      col = new boolean[N];
      diag1 = new boolean[2 * N - 1];
      diag2 = new boolean[2 * N - 1];
      backtracking(0); 
      System.out.println(ret);
      sc.close();
   }

---

📋 결과