[LeetCode] N-Queens

문제 설명

뭐 사실 너무 유명한 문제다.

Backtracking의 교과서라고 불릴정도로 아주 기본적인 유형이라고 생각한다.

오랜만에 알고리즘 뭐풀지 하다가 들어가서 풀어본 문제다.

개인적인 생각으론 BackTracking은 어느정도 유형에 들어서면 문제 수준이 비슷하다고 느껴지기 때문에 (스도쿠나, 변형스도쿠 처럼..)

DP나 Greedy로 문제가 안풀릴때 마지막으로 가져가야 혹은 (제일 처음 문제를 백트래킹으로 풀고, 최적화해야할) 라고 생각한다.

리턴값을 N-Queens가 놓인 String배열로 반환하라는 것도 재밌었다.

풀이 방법

BackTracking은 일단 찔러보고 안되면 안되는 경로까지 돌아갔다가 다른 경로로 가는 방법이다.

따라서 순환하는 부분과, 조건을 검사하는 부분으로 나눠서 구현하면 쉽게 구현할 수 있다.

Code

class Solution {
    
    
    List<List<String>> answer = new ArrayList<>();
    ArrayList<String> buffer = new ArrayList<>();
    
    int[][] directions = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };
    
    public List<List<String>> solveNQueens(int n) {
        char[][] check = new char[n][n];
        for(int i=0; i<check.length; i++){
            Arrays.fill(check[i],'.');
        }
        
        queens(check,0);
        
        
        return answer;
    }
    
    public boolean isGood(char[][] check,int x,int y){
        for(int[] direction : directions){
            if(!isOk(check,x+direction[0],y+direction[1],direction))
                return false;
        }
        return true;
    }
    
    public boolean isOk(char[][] check,int x, int y,int[] direction){
        if(x<0||y<0) return true;
        if(x>=check.length||y>=check.length) return true;
        if(check[x][y]=='Q') return false;
        return isOk(check,x+direction[0],y+direction[1],direction);
    }
    
    
    public void queens(char[][] check, int x){
        if(check.length == x){
            ArrayList<String> temp = new ArrayList<>(buffer);
            answer.add(temp);
            return;
        }
        
        for(int i=0; i<check[x].length; i++){
            if(isGood(check,x,i)){
                check[x][i] = 'Q';
                StringBuilder temp = new StringBuilder("");
                for(int j=0; j<check.length; j++)
                    temp.append('.');
                temp.setCharAt(i,'Q');
                buffer.add(temp.toString());
                queens(check,x+1);
                buffer.remove(x);
                check[x][i] = '.';
            }
        }
        
    }
}

결과