Programmers 12952 - N-Queen

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

프로그래머스

 

n개의 퀸이 서로를 공격할 수 없도록 배치하는 방법.

퀸을 순열로 배치하면 된다. 그런데 퀸을 배치할 때 고려해야 하는 요소는 무엇일까?

그건 바로 다른 퀸들의 위치이다. 퀸을 놓을 때 다른 퀸들을 공격할 수 있는 위치라면 놓아서는 안된다.

그렇다면 관리해야 할 것은? 이전에 놓았던 퀸들의 위치를 관리해야 한다. 어차피 같은 row에는 놓을 수 없으므로 퀸들의 위치는 1차원 배열로 col만 관리하면 될 것 같다.

1. row를 0~n까지 순회하면서 퀸을 놓을 col을 결정한다.
2. 이때 이전 row에 위치한 퀸들과의 관계를 고려해 퀸을 놓는다.

class Solution {
    
    static int[] cols;
    static int answer = 0;
    
    public int solution(int n) {
        cols = new int[n];
        dfs(0, n);
        return answer;
    }
    
    private void dfs(int row, int n) {
        if (row == n) {
            answer++;
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isPossible(row, col)) {
                cols[row] = col;
                dfs(row + 1, n);
                cols[row] = 0;
            }
        }
    }
    
    private boolean isPossible(int row, int col) {
        // row, col = 현재 놓을 위치
        for (int prevRow = 0; prevRow < row; prevRow++) {
            // 이전 row에 놓았던 것들
            int prevCol = cols[prevRow];
            
            if (col == prevCol) return false;
            if (row + col == prevRow + prevCol) return false;
            if (row - col == prevRow - prevCol) return false;
        }
        return true;
    }
}

주의해야 할 점은 직전 row에 대해서만 검사하는 것이 아니라 이전 모든 row들에 대해 검사를 진행해야 한다는 점이다.