[백준 9663] N-Queen(JAVA)

백준 9663번 문제 - N-Queen

9663번: N-Queen

---

문제 분석 

 

 

• N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수

---

해결 포인트

 

• 퀸이 공격할 수 있는 범위 상하좌우, 대각선 칸 수 제한 없이 무제한 !
• DFS 사용
• 가로, 세로 줄은 단순하게 퀸이 놓아졌으면 놓기 금지 - 가로,세로 확인할 수 있는 배열 구현
  • 가로 row[N]
  • 세로 col[N]
• 퀸을 놓은 곳의 가로, 세로 위치를 true로 설정 
  • 퀸 위치 x,y일 때, row[x] = true; col[y] = true;
• 대각선은 \ 선과 / 선, 2가지 존재 - 대각선도 그룹 제작
  • \ 선 diagonal1[N*2-1]
  • / 선 diagonal2[N*2-1]

 

 

• / 대각선 그룹 형성 방법 : x + y

 

 

• \ 대각선 그룹 형성 방법 : x - y

 

---

코드

 

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static int N;
    public static boolean [] diagonal1, diagonal2;
    public static boolean [] row, col;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        diagonal1 = new boolean[N*2-1];
        diagonal2 = new boolean[N*2-1];
        row = new boolean[N];
        col = new boolean[N];

        long result = 0;
        
        row[0] = true;
        for(int j=0;j<N;j++) {
            col[j] = true;
            diagonal1[j] = true;
            diagonal2[-j+N-1] = true;
            
            result += DFS(0, j, 1);
            
            col[j] = false;            
            diagonal1[j] = false;
            diagonal2[-j+N-1] = false;
        }

        bw.write(result+"\n");
        bw.flush();
        bw.close();
    }
 
    public static int DFS(int x, int y, int count) {
        if(count == N)
            return 1;
        
        int result = 0;

        int i = x+1;
        row[i] = true;
        for(int j=0;j<N;j++) {
            if(col[j]) continue;
            if(checkRoundQ(i,j)) {
                col[j] = true;
                diagonal1[i+j] = true;
                diagonal2[i-j+(N-1)] = true;
                
                result += DFS(i,j, count+1);
                
                col[j] = false;
                diagonal1[i+j] = false;
                diagonal2[i-j+(N-1)] = false;
            }
        }
        row[i] = false;
        
        return result;
    }

    public static boolean checkRoundQ(int x, int y) {
        if(diagonal1[x+y]) return false;
        if(diagonal2[x-y+(N-1)]) return false;
        
        return true;
    }
}