백트래킹

sewa 2806. N-Queen

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    static int[][] board;
    static int n;
    static int cnt;
    static boolean[] check;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 

            n = Integer.parseInt(br.readLine());
            board = new int[n][n];
            check = new boolean[n];
            cnt=0;
             
            put(0, 0);
            System.out.println(cnt);
 
    } // main
 
    static void put(int Q, int row) {
    	if (Q == n) {
    		// 모든 퀸을 판에 놓았다.
    		cnt++;
    		return;
    	}

        for(int j=0; j<n; j++) {
        	if(deltaCheck(row, j)) {
		        board[row][j] = 1;
		        check[row] = true;
		        put(Q + 1, row+1);
		        board[row][j] = 0;
		        check[row] = false;
        	}
        }
    }
    
    static boolean deltaCheck(int i, int j) {
        int r = i;
        int c = j;
        
        // 열 검사
        while (r > 0) {
            if (board[--r][j] == 1)
                return false;
        }
 
        // 오른쪽 대각선 검사
        r = i;
        while (r > 0 && c < n - 1) {
            if (board[--r][++c] == 1)
                return false;
        }
 
        // 왼쪽 대각선 검사
        r = i;
        c = j;
        while (r > 0 && c > 0) {
            if (board[--r][--c] == 1)
                return false;
        }
 
        return true;
    }
 
}