프로그래머스 N-Queen 자바 풀이

https://programmers.co.kr/learn/courses/30/lessons/12952?language=java 

코딩테스트 연습 - N-Queen

알고리즘 수업에서 배웠던 백트래킹 알고리즘의 기본 문제 N-Queen.

간만에 한 거라 기억이 잘 나지 않아 블로그를 참고해서 풀었다. 기존에 하던 방식이라 그런지 이해하는데 큰 어려움은 없었다.

대각선 확인하는 방법이 신박했다! 그리고 2차원 배열이 아니라 1차원 배열을 이용한 방식도. 훨씬 간단하고 편리한 방법이다!

class Solution {

    int[] col;
    int answer;

    public int solution(int n) {
        answer = 0;

        for(int i = 0; i < n; i ++) {
            col = new int[n];
            col[0] = i;
            bcktrk(n, 1);
        }

        return answer;
    }

    private void bcktrk(int max, int row) {

        if(max == row) {
            answer ++;
            return;
        }

        for(int i = 0; i < max; i ++) {
            col[row] = i;
            if(isPossible(row))
                bcktrk(max, row + 1);
        }
    }

    private boolean isPossible(int row) {
        for(int i = 0; i < row; i ++) {
            if(col[i] == col[row]) return false; //윗 행 확인
            if(Math.abs(i - row) == Math.abs(col[i] - col[row])) return false; //대각선 확인(행의 증가량, 열의 증가량이 같으면 대각선)
        }
        return true;
    }
}