N Queens

전형적인 n queen 문제이다

1차원배열을 이용해서 2차원 좌표를 저장할수있다.

1차원의 인덱스는 행, 1차원 인덱스의 value값을 열값이라고 칭하면 된다.

그럼 Recursion을 이용하여 각 행마다 퀸을 계속놓는다고 가정할때, 더이상 끝을 놓을수 없을때 그때 답이 된다는 것을 알고있다.

그러면, 각 행마다 열의 위치를 놓아줘야 하는데, 이 경우의수를 다하게되면 시간초과가 난다

그래서 백트래킹을 이용해서 가지치기를 해줘야 한다.

안되는 조건은 2가지를 보면된다.

1. 열의 좌표가 같은경우(어차피 행은 애초에 다른 행이니까 , 상관이 없다)
2. 대각선을 그었을때 퀸에게 잡히는 경우(현재 새로운위치의(x,y)와 이전 퀸들의 위치(a,b)라고 할때, 절대값 (x-a)와 (y-b)가 일치하는경우)

이 2가지 조건을 빼면 N queen을 만족할수 있다.
그때 만족하는 퀸 모양의 형태를 List타입으로 적절하게 뽑아내는 것도 중요하다

by Java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        int[] arr = new int[n];
        List<List<String>> ans = new ArrayList<>();
        go(0,n,arr,ans);
        return ans;
    }
    private void go(int index,int depth,int[] arr,List<List<String>> ans) {
        if(index==depth) {
            char[][] board = new char[depth][depth];
            for(int i=0;i<depth;i++) {
                for(int j=0;j<depth;j++) {
                    board[i][j]='.';
                }
            }
            for(int i=0;i<arr.length;i++) {
                board[i][arr[i]-1]='Q';
            }
            List<String> temp = new ArrayList<>();
            for(int i=0;i<depth;i++) {
                StringBuilder sb = new StringBuilder();
                for(int j=0;j<depth;j++) {
                    sb.append(board[i][j]);
                }
                temp.add(sb.toString());
            }
            ans.add(temp);
            return;
        }
        for(int i=1;i<=depth;i++) {
            arr[index] = i;
            if(check(index,arr)) {
                go(index+1,depth,arr,ans);
            }
            else arr[index]=0;
        }
        
    }
    private boolean check(int index,int[] arr) {
        for(int i=0;i<index;i++) {
            if(arr[i]==arr[index] || Math.abs(i-index)==Math.abs(arr[i]-arr[index])) return false;
        }
        return true;
    }
}