[프로그래머스] N-Queen (08.21)

문제

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

코딩테스트 연습 - N-Queen

 

접근법

백트래킹에서 가장 대표적인 예로 나오는 N-Queen 문제이다.

대표적인 백트래킹 문제임에도 풀기가 힘들었다.

처음에는 이차원 배열을 사용해서 풀려고 했는데 복잡했고

col이라는 일차원 배열을 만들어서 col의 값을 row 인덱스를 배열에 넣어주었다.

ex) col = { 2, 4, 1, 3}

같은 라인 또는 대각라인에 여왕이 존재하면 안되기 때문에 그 부분을 처리해주는 것이 까다로웠다.

자세한 설명은 코드에 주석으로 달아놓았다.

 

코드

class Solution {
    private int col[];
    private int cnt=0;
    private int n;
    public int solution(int n) {
        this.n = n;
        //col을 1부터 n까지 적용시킨다.
        for(int i=1;i<=n;i++){
            col = new int[n+1];
            col[1] = i;
            dfs(1);
        }
        return cnt;
    }

    private void dfs(int row) {
        if(row == n){
            cnt++;
            return;
        }

        for(int i=1;i<=n;i++){
            //우선 컬럼 i를 다음 row의 컬럼으로 지정해놓고
            col[row+1] = i;
            //가능하다면
            if(isPossible(row+1)){
            	//재귀
                dfs(row+1);
            //불가능하다면 다시 0으로 지정 ( 백트래킹 )
            }else{
                col[row+1] = 0;
            }
        }
        //row의 컬럼 값을 0으로 지정 ( 백트래킹 )
        col[row] = 0;
    }

    private boolean isPossible(int row){
        int idx = 1;

        while(idx < row){
            //앞의 조건은 같은 컬럼에 걸치는지를 확인
            //뒤의 조건은 대각선에 걸치는지를 확인
            if(col[row] == col[idx] || Math.abs(col[row] - col[idx]) == row-idx)
                return false;
            idx++;
        }
        return true;
    }
}