[Dev-Ping9] 백준 9663번 - N-Queen (Java) [DFS]

 

 

# 문제 설명

 퀸들은 같은 대각선과 같은 직선에 있으면 안된다. (조건)

 

 경우의 수를 물으므로 완전탐색을 진행하여야 한다.

 

 완전 탐색을 진행하면서 (조건) 에 부합하는지 검사 한 후,

 (조건)에 부합한다면 계속 진행하며

 (조건)에 부합하지않으면 해당 Path로의 탐색은 중지한다. (BackTracking)

 

 

# 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    static boolean[] boardColVisited;
    static int[] queens;

    static boolean isPromising(int i, int currentNode){
        //1 . 대각선(노드번호의 차이랑 실제 놓여져있는 노드값의 차이가 같을때)  2. 직선 (boardColVisited)
        if(boardColVisited[i]) return false; // 직선

        int k =1;
        while(k<currentNode){ //현재노드 전까지 싹 검사
            if(Math.abs(currentNode-k) == Math.abs(queens[k]-i)){ // 대각선 
                return false;
            }
            k++;
        }
        return true;
    }

    static int cnt =0;

    static void printArr(int[] arr){
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    static void dfs(int currentNode, int boardLength){
        if(currentNode==boardLength+1){
            // printArr(queens);
            cnt++;
            return;
        }

        for(int i=1; i<=boardLength; i++){
            if(isPromising(i, currentNode)){
                queens[currentNode] = i;
                boardColVisited[i]= true;
                dfs(currentNode+1,boardLength);
                boardColVisited[i]= false;
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        queens = new int[n+2];
        boardColVisited = new boolean[n+2];

        dfs(1, n);
        System.out.println(cnt);
    }
}