LeetCode: 51번 (N-Queens) [JAVA]

문제 링크

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

N-Queens - LeetCode

풀이

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

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

 문제 특성 상 퀸들이 서로 공격을 받지 않는 위치에 존재해야 하기 때문에, 애초에 퀸을 놓으면서 공격을 절대 안받는 위치에 놓기 보다는, 어느정도만 고려하여 퀸을 배치하고 이후 최종적으로 다시 체크하는 것으로 풀이를 작성했다. 우선 퀸의 이동방향의 경우 상하좌우 및 대각선 이동이 모두 가능하기 때문에, 고려할 방향이 많다. 다만 쉽게 생각할 수 있는 부분이 상화좌우인데, 이 부분은 단순히 특정 행과 열에 퀸을 놓게 되면 해당 행과 열에 방문 표시를 체크하고, 이후 다음 행에 퀸을 놓을 때는 해당 열을 피해 퀸을 놓으면 된다. 이를 위해 우선 입력받는 n에 대해 이차원 체스판('.'으로 초기화)과, n 크기의 행과 열 체크용 배열을 초기화한다.
 이후 퀸을 체스판에 놓는 시뮬레이션 함수를 구현한다. 우선 인자로 받는 nextRow는 현재 퀸을 놓을 행의 인덱스를 의미하며, 해당 행이 n에 도달하면 퀸을 모두 체스판에 놓은 것으로 전체 체스판에 대한 체크를 진행하면 된다. 이후 해당 체스판이 조건에 맞다면, 이를 문제 요구에 맞게 List<String> 형태로 바꾼 다음 답에 추가한다. 다음 퀸을 놓을 로직의 경우 백트래킹 기반으로 함수를 작성하는데, 해당 행의 열을 모두 탐색하며 만약 해당 열에 퀸을 놓은 적이 없다면, 해당 위치에 퀸을 놓고 배열에 체크를 해준 다음 다음 행에 대한 탐색 함수를 call 한다.
 다음 체스판 체크 함수의 경우, 앞선 퀸을 놓는 과정에서 간단한 상하좌우의 중복을 피해 퀸을 놓았기 때문에 대각선 이동만 고려하여 체크하면 된다. 물론 이마저도 위에서부터 순차적으로 내려오기 때문에, 4가지 대각선 방향 중 왼쪽 아래와 오른쪽 아래 방향만을 체크하면 된다. 전체 배열을 돌다 해당 위치가 퀸인 경우 해당 위치부터 아래 방향 대각선의 위치들을 체크하며, 만약 해당 위치에 퀸이 존재하면 false를 반환하면 된다. 탐색이 모두 끝났으면 오류가 없기 때문에, true를 반환하면 된다.
 해당 함수들을 모두 구현했다면, 메인 함수에서는 단순히 시작 행(0)을 기준으로 시뮬레이션 함수를 요청한 다음 이에 따른 결과를 반환하면 된다.

 

class Solution {
    char[][] chessboard;
    boolean[] usedRow, usedCol;
    List<List<String>> answer = new ArrayList<>();

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

        simulation(0, n);
        return answer;
    }

    void simulation(int nextRow, int n) {
        if (nextRow == n) {//모든 퀸 배정 완료
            if (check(n)) {//유니크한 상태라면 답에 추가
                List<String> temp = new ArrayList<>();
                StringBuilder sb = new StringBuilder();

                for (int i = 0; i < n; i++) {
                    sb.setLength(0);
                    for (int j = 0; j < n; j++) {
                        sb.append(chessboard[i][j]);
                    }
                    temp.add(sb.toString());
                }

                answer.add(temp);
            }
            return;
        }

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

결과