[프로그래머스] N-Queen -자바(JAVA)

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

코딩테스트 연습 - N-Queen

 

문제 해석

백트레킹에서 유명한 N-Queen 문제입니다.

 

가로, 세로 길이가 n인 정사각형 체스판이 존재합니다.

 

체스판 위에 n개의 퀸이 서로 공격할 수 없도록 배치하고 싶습니다.

 

만약 n = 4인 경우 다음과 같이 퀸을 배치하면 퀸은 서로를 한 번에 공격할 수 없습니다.

n이 매개변수로 주어질 때 n개의 퀸이 조건에 만족하도록 배치합니다.

 

n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return 하세요

 

퀸은 가로, 세로, 대각선으로 이동할 수 있습니다.

 

 

코드

class Solution {
    static int answer = 0;
    static int n;
    public int solution(int n) {
        
        this.n = n;
        int[][] chessBoard = new int[n][n];
        findAnswer(0, chessBoard);                
        return answer;
    }
    
      private static void findAnswer(int cnt, int[][] chessBoard) {
        if (cnt == n) {
            answer++;
            return;
        }
        for (int i = 0; i < n; i++) {
                if (canPutQueen(cnt, i, chessBoard)) {
                    chessBoard[cnt][i] = 1;
                    findAnswer(cnt + 1, chessBoard);
                    chessBoard[cnt][i] = 0;
                }
        }


    }

    private static boolean canPutQueen(int y, int x, int[][] chessBoard) {
        int[] dy = {-1, -1, 1, 1, -1, 1, 0, 0};
        int[] dx = {-1, 1, -1, 1, 0, 0, -1, 1};

        //대각선 검사 + 가로세로 검사
        //0~3현재 좌표에서 왼쪽위 오른쪽위 왼쪽아래 오른쪽아래 순서대로 검사함
        //4~7 현재 좌표에서 상 하 좌 우 순서대로 검사함
        for (int k = 0; k < 8; k++) {
            int ny = y;
            int nx = x;
            while (true) {
                ny += dy[k];
                nx += dx[k];

                if (!isPosValid(ny, nx)) {
                    break;
                }

                if (chessBoard[ny][nx] == 1) {
                    return false;
                }
            }
        }

        return true;
    }

    private static boolean isPosValid(int ny, int nx) {
        return ny >= 0 && ny < n && nx >= 0 && nx < n;
    }
}