LeetCode: 52번 (N-Queens II) [JAVA]

문제 링크

https://leetcode.com/problems/n-queens-ii/

N-Queens II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 입력받은 n을 바탕으로 nxn 크기의 체스판(모두 '.'으로 초기화), n 크기 정도의 열 체크 표시 배열 생성
2. 체스판에 퀸을 놓는 시뮬레이션 함수 생성
   1) 행이 n만큼 왔다면, 모든 퀸을 배정 완료했기 때문에 해당 체스판이 조건에 부합한지 체크. 만약 부합하면 답 + 1
   2) 특정 행을 기준으로 열을 모두 돌며, 해당 열에 퀸이 놓인 적이 없다면 퀸을 놓고 다음 행 탐색을 진행(백트래킹)
3. 현재 체스판이 조건에 부합한지 체크하는 함수 생성
   1) 마지막 행을 제외한 전체 행, 열 속에서 퀸을 탐색
   2) 퀸을 발견하면, 해당 퀸을 기준으로 왼쪽 아래, 오른쪽 아래 방향으로 격자를 확인해 해당 구간에 퀸이 존재하면 false 반환
   3) 최종적으로는 true 반환
4. 시작 행(0)을 기준으로 시뮬레이션 진행, 이후 답 반환

 다른 문제로 구분됐지만, 51.N-Queens 문제와 내용 자체가 동일하고 다만 반환하는 답의 방식에만 차이가 있어, 큰 흐름의 로직은 동일하게 구성했다. 다만 변화점이라고는 기존에는 백트래킹을 할 때 행과 열을 모두 체크했던 것을, 추후 다시보니 로직 상 행을 체크하는 것이 필요가 없어 그 부분을 제거하는 정도만 진행했다.

 

class Solution {
    char[][] chessboard;
    boolean[] usedCol;
    int answer = 0;

    public int totalNQueens(int n) {
        chessboard = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(chessboard[i], '.');
        }
        usedCol = new boolean[n];

        simulation(0, n);
        return answer;
    }

    void simulation(int nextRow, int n) {
        if (nextRow == n) {//모든 퀸 배정 완료
            if (check(n)) {//유니크한 상태라면 답에 추가
                ++answer;
            }
            return;
        }

        for (int i = 0; i < n; i++) {//해당 행에 속한 열을 모두 돌며
            if (!usedCol[i]) {//퀸을 놓을 수 있는 자리면 퀸을 놓고 다음 행 탐색(백트래킹)
                usedCol[i] = true;
                chessboard[nextRow][i] = 'Q';
                simulation(nextRow + 1, n);
                chessboard[nextRow][i] = '.';
                usedCol[i] = false;
            }
        }
    }

    boolean check(int n) {
        for (int i = 0; i < n - 1; i++) {//마지막을 제외한 전체 행을 돌며
            for (int j = 0; j < n; j++) {
                if (chessboard[i][j] == 'Q') {//퀸 위치면
                    int step = 1;

                    while (i + step < n) {//해당 퀸부터 대각선으로 내려오는 방향의 위치들에 대해
                        if (j - step >= 0) {//왼쪽 아래 방향
                            if (chessboard[i + step][j - step] == 'Q') {//퀸이 중복
                                return false;
                            }
                        }

                        if (j + step < n) {//오른쪽 아래 방향
                            if (chessboard[i + step][j + step] == 'Q') {//퀸이 중복
                                return false;
                            }
                        }
                        ++step;
                    }

                    continue;//해당 행 건너뛰기
                }
            }
        }

        return true;
    }
}

결과