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

백트랙킹 문제입니다.

 

N이 주어질 때, 크기가 N*N인 이차원 배열에서 N개의 퀸이 놓여질 수 있는 경우의 수를 구하는 문제입니다.

퀸은 다음과 같은 특징을 지니고 있습니다.

• 하나의 퀸이 놓여진 직선에는 다른 퀸이 놓여질 수 없다.
• 하나의 퀸이 놓여진 대각선에는 다른 퀸이 놓여질 수 없다.

퀸은 각 행과 열에서 오직 하나만 존재할 수 있기 때문에, 이차원 배열을 일차원 배열로 압축할 수 있습니다.

일차원 배열의 '행(row)'는 이차원 배열과 같이 '행(row)'을 의미하면 되고, 

일차원 배열의 값은 해당 퀸이 놓여져 있는 '열(column)'의 위치를 의미하면 됩니다.

 

즉, 일차원 배열의 '행(row)'에 대한 값은 퀸이 놓여져 있는 '열(colimn)'을 의미합니다.

// 배열의 값은 해당 행의 queen이 있는 '열(column)'을 의미함
board = new int[n];

퀸을 놓을 때에는 해당 위치의 직선, 대각선에 다른 퀸이 존재하지 않는지 확인해야 합니다.

직선은 배열의 값을 비교하면 되고,

대각선은 기울기를 비교하면 됩니다.

private static boolean valid(int i) {
    for (int j = 0; j < i; j++) {
        if (board[i] == board[j]) return false; // 직선
        if (Math.abs(i - j) == Math.abs(board[i] - board[j])) return false; // 대각선
    }
    return true;
}

 

[구현 코드]

class Solution {
    private static int[] board;
    private static int answer;

    public static int solution(int n) {
        // 배열의 값은 해당 행의 queen이 있는 '열(column)'을 의미함
        board = new int[n];

        backTracking(0, n);

        return answer;
    }

    // depth는 행을 의미함
    private static void backTracking(int depth, int n) {
        if (depth == n) {
            answer++;
            return;
        }
        for (int i = 0; i < n; i++) {
            board[depth] = i; // 해당 depth(행)과 i(열)에 퀸을 놓을 수 있는지 확인
            if (valid(depth)) {
                backTracking(depth + 1, n);
            }
        }
    }

    private static boolean valid(int i) {
        for (int j = 0; j < i; j++) { // 마지막으로 놓여진 것과 이전의 것들을 비교
            if (board[i] == board[j]) return false;
            if (Math.abs(i - j) == Math.abs(board[i] - board[j])) return false;
        }
        return true;
    }
}