Lv 2. N-Queen

 

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

 

 

이 문제는 N이 주어질 때

N개의 Queen을 서로 공격할수 없는 경로에 놓는 방법의 수를 구하는 문제다.

DFS와 백트래킹을 활용하여 문제를 해결하였다.

 

1번째로 DFS method다.

이문제를 보고 풀이도중 생각이 되는것이

하나의 줄에 하나의 Queen이 존재해야한다는 생각이 들었다.

0에서 N-1 까지 순회하면서 만약 dfs 의 파라미터인 depth줄에 i 번째 board가

놓을수 있는 곳이라면 재귀를 통해 다음 dfs로 depth+1 하여 들어가게 된다.

dfs로 들어가기전 checkboard를 통해 깊은 복사된 board를 들고 들어간다.

 

dfs를 들어왔다면 howManyLeft method를 통해서 현재 남아있는 칸이 몇개인지 

확인하는 method를 통해서 남은 queen의 갯수와 빈칸의 갯수를 비교하여 백트래킹을 하여 가지치기를 한다.

 

checkboard에서는 깊은 복사를 통해 queen의 이동경로 상하좌우 대각선의 경로에 board를 체크하고 그 체크된 board를 리턴하여 다음 dfs에 사용될 수 있도록 한다.

그리하여 모든 조건이 완성되어 depth가 n이 된다면 answer를 증가시켜

 

answer가 정답이 될수 있게 풀이하였다.

 

 

class Solution {
    
    int n, answer = 0;
        
    int howManyLeft(boolean[][] board){
        int value = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++)
                if(!board[i][j]) value++;
        }
        return value;
    }
        
    boolean[][] checkBoard(int x, int y, boolean[][] origin){
        boolean[][] board = new boolean[n][n];
        for(int i = 0 ; i < n ; i++)
            board[i] = origin[i].clone();
        
        for(int i = 0 ; i < n ; i++){
            board[x][i] =true;
            board[i][y] =true;
        }
        for(int i = 1 ; i < n ; i++){
            if(x-i >= 0 && y-i >= 0 && !board[x-i][y-i]){ board[x-i][y-i]=true;}
            if(x-i >= 0 && y+i < n && !board[x-i][y+i]){ board[x-i][y+i]=true;}
            if(x+i < n && y-i >= 0 && !board[x+i][y-i]){ board[x+i][y-i]=true;}
            if(x+i < n && y+i < n && !board[x+i][y+i]){ board[x+i][y+i]=true;}
        }
        return board;
    }
    
    void dfs(int depth, boolean[][] board){
        if(depth == n){
            answer++;
            return;
        }
        if(n-depth > howManyLeft(board)) return;
         for(int j = 0 ; j < n ; j++){
            if(!board[depth][j]) {
                dfs(depth+1,checkBoard(depth,j,board));
            }
        }
        return;
    }
    
    public int solution(int n) {
        this.n = n;
        boolean[][] board = new boolean[n][n];
        dfs(0,board);
        return answer;
    }
}