[BOJ] 9663. N-Queen

백트래킹의 전형적인 문제인 N-Queen 문제이다.

체스판에 서로 공격할 수 없도록 N개의 Queen을 배치하는 문제인데, Queen의 움직임 특성상 한 행에 한 개의 Queen 만을 가질수 있게 됨으로 한행을 depth로 보고 dfs를 실행하였다. 보통의 백트래킹은 visit함수로만 방문 여부를 결정하였는데 이 문제에선 대각선이랑 같은 열에 Queen이 존재해야하는지 봐야함으로 check함수를 이용하여 방문 가능여부를 한번더 확인해주는 과정을 거쳐 문제를 해결하였다. 

package chap07;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_9663_NQueen {
    
    static boolean[][] visit;
    static int N;
    static int count;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        
        visit=new boolean[N][N];
        count=0;
        
        dfs(0);
        System.out.println(count);
        
    }
    
    static void dfs(int depth) {
        if(depth==N) {
            count++;
            return;
        }
        for(int col=0;col<N;col++) {
            if(visit[depth][col]==false && check(depth,col)==true) {
                visit[depth][col]=true;
                dfs(depth+1);
                visit[depth][col]=false;
            }
        }
    }
    
    static boolean check(int row,int col) {
        for(int len=1;len<=row;len++) {
            if(visit[row-len][col]==true) {
                return false;
            }
            if(col-len >= 0 && visit[row-len][col-len]==true) {
                return false;
            }
            if(col+len <N && visit[row-len][col+len]==true) {
                return false;
            }
        }
        return true;
    }
    
}