[Leet Code] N Queens II

안녕하세요. 오늘은 5월 5주차 첫번째 알고리즘인 N Queens II 풀이를 작성해보겠습니다 :)

문제

요약
n x n 배열 안에서 n 개의 퀸이 서로 공격할 수 없는 위치에 놓일 수 있도록 배치하는 방법의 개수를 모두 찾아 return하는 문제입니다.

처음 생각한 방법

사실, 처음에는 퀸이 어떻게 동작하는지 몰라서 찾아봤습니다.
상하좌우, 대각선들까지 쭉 비어있어야하는 것이더라고요.

그래서 처음에는 n x n 배열을 만들고, 그 안에서 첫 행에 퀸을 하나씩 놓아가면서 dfs 방식으로 퀸의 위치를 찾았습니다.

풀리긴 했지만, 코드가 너무 복잡했고 사실 저도 이해가 잘 되지 않아 답을 찾아보기 시작했습니다.

다른 분 코드 참고

알고리즘 포스팅을 하면서, 다른 분의 코드를 참고한 경우는 처음인데요, 워낙 자주 나오는 유형이라고 해서 효율적인 코드를 참고하려고 했습니다.

우선 n x n 배열이 아닌 n 배열을 사용합니다.
배열의 index는 행, index에 저장된 값은 열로 생각하는 방법입니다.
예시로, array[1] = 3 이라면 1번째 행의 3열에 퀸이 위치하고 있다는 것입니다.
그리고 퀸의 위치 체크는 다른 인덱스에 해당 행의 인덱스 값이 저장되어있다면 같은 행에 있는지 확인합니다.
대각선 체크는, 현재 행과 앞선 행의 차이가 현재 행의 열 값과 앞선 열 차이가 같다면 대각선에 있다는 것입니다.

코드 설명

int result = 0;

클래스의 전역 변수로 result 를 선언해줍니다.

private void placeQueens(int[] array, int row, int n) {
    if (row == n) {
        result++;
        return;
    }
    for (int i = 0; i < n; i++) {
        array[row] = i;
        if (checkValidation(array, row)) {
            placeQueens(array, row + 1, n);
        }
    }
}

퀸을 놓는 과정의 함수 placeQueens 입니다.
row 가 n 이라면 모든 퀸이 놓여졌다는 것입니다. 따라서 result 에 값을 하나 추가해주고 return 합니다.
모든 퀸이 놓아지지 않았다면, for문을 순회하면서 재귀호출합니다.
row 의 값을 i 로 설정한 후에 배열의 유효성 검사를 합니다. 퀸의 위치 검사겠죠?
만약 true 결과가 나왔다면 재귀호출을 진행합니다.

private boolean checkValidation(int[] array, int row) {
    for (int i = 0; i < row; i++) {
        if (array[i] == array[row] || row - i == Math.abs(array[i] - array[row])) {
            return false;
        }
    }
    return true;
}

퀸의 위치 검사를 진행하는 checkValidation 함수입니다.
array[i] == array[row] 는 같은 열에 퀸이 놓여져있는지 확인하는 함수입니다.
같은 행은 검사하지 않습니다. 그 이유는 index 자체가 행이기 때문에 중복 검사가 의미가 없기 때문입니다.
row - i == Math.abs(array[i] - array[row]) 는 대각선에 위치하는지 검사하는 것입니다.
앞선 행에 저장된 값과 현재 행에 저장된 값의 차이가 row - i 라면 대각선에 위치하는 것입니다.

전체 코드

class SolutionNQueens {
    int result = 0;

    // 0: 비어있음 1: 퀸 있음 -1: 퀸 못놓음
    public int totalNQueens(int n) {
        placeQueens(new int[n], 0, n);
        return result;
    }

    private void placeQueens(int[] array, int row, int n) {
        if (row == n) {
            result++;
            return;
        }
        for (int i = 0; i < n; i++) {
            array[row] = i;
            if (checkValidation(array, row)) {
                placeQueens(array, row + 1, n);
            }
        }
    }

    private boolean checkValidation(int[] array, int row) {
        for (int i = 0; i < row; i++) {
            if (array[i] == array[row] || row - i == Math.abs(array[i] - array[row])) {
                return false;
            }
        }
        return true;
    }
}

마무리

제가 처음 생각한 2차원 배열로 진행한 분들도 꽤 많았던 것으로 기억합니다.
하지만 Leet Code에서는 타임 오버가 발생해서 1차원 배열이라는 방법을 찾을 수 있었던 것 같습니다.
효율적인 코드를 찾은 것 같아 너무 좋네요 ㅎ.ㅎ

이번 포스팅도 읽어주셔서 감사합니다 :) !!