class Solution {

    static int answer;

    public int solution(int n) {

        answer = 0;

        int[][] chessboard = new int[n][n];

        placeQueen(chessboard,0);

        //n개의 조합으로 만들 수 있는 모든 경우의 중복을 제거하기 위해 answer n!으로 나눠줘야함

        answer /= factorial(n);

        return answer;

    }


    public static boolean canPlaceQueen(int[][] chessboard, int row, int col){

        for(int i = 0 ; i < chessboard.length ; i++){

            //가로, 세로에 존재하면 불가능

            if(chessboard[row][i] == 1 || chessboard[i][col] == 1) return false;

            //대각선에 존재하면 불가능

            if(row-i >= 0 && col-i >= 0 && chessboard[row-i][col-i] == 1) return false;

            if(row+i < chessboard.length && col-i >= 0 && chessboard[row+i][col-i] == 1) return false;

            if(row-i >= 0 && col+i < chessboard.length && chessboard[row-i][col+i] == 1) return false;

            if(row+i < chessboard.length && col+i < chessboard.length && chessboard[row+i][col+i] == 1) return false;

        }

        return true;

    }


    public static void placeQueen(int[][] chessboard, int count){

        if(count == chessboard.length){

            answer++;

            return;

        }

        for(int i = 0 ; i < chessboard.length ; i++){

            for(int j = 0 ; j < chessboard.length ; j++){

                if(canPlaceQueen(chessboard,i,j)) {

                    chessboard[i][j] = 1;

                    placeQueen(chessboard, count+1);

                    chessboard[i][j] = 0;

                }

            }

        }

    }


    public static int factorial(int n){

        if(n == 1) return 1;

        return n * factorial(n-1);

    }

}



이번 알고리즘 시험범위라 책안보고 백트래킹으로 짜봤는데 프로그래머스에서 다른건 전부 맞는데 틀린건 전부 시간초과걸림

실행시간 줄여야 할 거 같움 ㅇㅅㅇ 

첫번째 생각나는거 : chessboard를 1차원배열로 수정해서 현재 인덱스에 퀸을 놓으면 그 다음 인덱스부터 퀸을 놓도록 변경하여 중복된 경우의 수 배제(지금은 2차원이라 0부터 다시 다돌아서 같은 조합이 생김, 그래서 팩토리얼로 나눴음)

두번째 생각나는거 : canPlaceQueen메서드에서 대각선 확인하는 알고리즘 뭔가 더러운데 개선 어떻게 할 수 없을지?