N-Queen (Java, Backtracking, 프로그래머스)

DFS + Pruning을 이용하여 푸는 백트래킹 문제였다.

2차원 배열을 다루는 문제이므로 2차원 배열을 선언하여 x,y 값에 따라 퀸을 놓는 플래그를 세워서 푸는 방법도 있겠지만 아래의 풀이 방법은 두 개의 축 중 하나를 고정시켜서 마치 1D의 배열을 푸는 것처럼 이용하는 방식이다.

여기서 값을 저장할 1D 배열은 index로 row 값을 갖고 index의 value로 col을 갖는다.

 

풀이의 흐름은 다음과 같다.

 

1. 가능한 한 많은 변수를 전역변수화시킨다. 해당 문제에서는 파라미터 n, return 할 answer, row와 col 값을 저장하는 1D 배열을 선언한다.

 

2. DFS로 row를 아규먼트로 넘긴다. (0, 0)부터 시작할 것이므로 0을 넘김.

 

3. DFS에서는 언제나 탈출 조건과 반복 조건을 설정한다. 이때 중요한 것은 pruning을 탈출 조건에서 하는 것이 아닌 반복 조건에 걸어 진입을 하지 않게 하는 것이다.

3-1. 파라미터로 넘겨지는 값이 inner loop, for 문으로 도는 값이 outer loop라고 생각하면 이해하기 수월하다.

3-2. 파라미터로 넘겨지는 row가 n과 같아질때 즉 inner loop가 한 바퀴를 다 돌았을때 해당 콜스택을 탈출하면서 answer++을 한다.

3-3. cols[row] = col;은 (row, col)의 값을 (index, value)의 형태로 저장하는 것이다.

3-4. row의 promising을 체크하고 유망하지 않다면 가지치기가 들어간다. 

 

4. check(int position)으로 문제의 조건에 부합한지를 체크한다.

4-1. 현재 인덱스 이후에는 어떠한 말도 존재하지 않으므로 현재 인덱스까지만 for loop를 수행하며 조건을 체크한다.

4-2. cols에 저장된 (index, value)가 같다면, 이미 해당 열에 존재한다면 promising하지 않으므로 false

4-3. x1 - x2 == y1 - y2 하다는 것은 대각선에 위치해있다는 것을 의미하므로 return false

 

class Solution {
    int n, answer;
    int[] cols;
    public int solution(int n) {
        this.n = n;
        cols = new int[n];
        answer = 0;
        
        dfs(0);
        
        return answer;
    }
    void dfs(int row) {
        if (row == n) {
            answer++;
            return;
        }
        for (int col = 0; col < n; col++) {
            cols[row] = col;
            if (check(row)) dfs(row + 1);
        }
    }
    boolean check(int position) {
        for (int row = 0; row < position; row++) {
            if (cols[row] == cols[position]) return false;
            if (Math.abs(row - position) == Math.abs(cols[row] - cols[position])) return false;
        }
        return true;
    }
}