[LeetCode] 51 N-Queens(Java)

1. 문제 설명

문제 링크: LeetCode 51 - N-Queens

요약: $n \times n$ 체스판에 $n$개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 찾는 문제입니다. 퀸은 같은 행, 열, 그리고 양방향 대각선 위에 있는 기물을 공격할 수 있습니다.

2. 핵심 아이디어

이 문제는 대표적인 백트래킹(Backtracking) 문제입니다. 모든 위치를 다 시도해보되, 퀸을 놓을 수 없는 조건이 되면 즉시 되돌아가서 다른 경로를 탐색합니다.

• 행별 배치: 퀸은 같은 행에 존재할 수 없으므로, 0번 행부터 $n-1$번 행까지 한 행에 하나씩 퀸을 배치하며 내려갑니다.
• 공격 가능 여부 체크: 현재 위치(row, col)에 퀸을 놓을 수 있는지 판단하기 위해 기존에 배치된 퀸들과 비교합니다.
  • 같은 열: queen.col == col
  • 우상향 대각선 ($/$): 두 좌표의 합이 같음 (row + col)
  • 우하향 대각선 ($\backslash$): 두 좌표의 차가 같음 (row - col)
• 상태 복구: 특정 위치에 퀸을 놓고 재귀 호출(recall)을 한 뒤에는, 반드시 놓았던 퀸을 제거(queens.removeLast())하여 다음 선택지를 깨끗한 상태에서 탐색할 수 있도록 합니다.

3. 코드

class Solution {
    List<List<String>> ret;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        List<List<Integer>> queens = new ArrayList<>();
        recall(n, queens, 0);

        return ret;
    }

    private void recall(int n, List<List<Integer>> queens, int row) {
        // 1. 기저 조건: 모든 행에 퀸을 다 배치했을 때
        if (row >= n && queens.size() == n) {
            List<String> sl = getStrings(n, queens);
            ret.add(sl);
            return;
        }
        
        // 2. 현재 행(row)에서 각 열(col)에 퀸을 놓아보기
        for (int col = 0; col < n; col++) {
            if (isPosable(queens, row, col)) {
                queens.add(List.of(row, col)); // 퀸 배치
                recall(n, queens, row + 1);    // 다음 행으로 이동
                queens.removeLast();           // 백트래킹 (원태 복귀)
            }
        }
    }

    // 퀸의 위치 리스트를 문제에서 요구하는 문자열 리스트 포맷으로 변환
    private static List<String> getStrings(int n, List<List<Integer>> queens) {
        List<String> sl = new ArrayList<>();
        for (int row = 0; row < queens.size(); row++) {
            List<Integer> queen = queens.get(row);
            StringBuilder sb = new StringBuilder();
            for (int col = 0; col < n; col++) {
                if (queen.get(0) == row && queen.get(1) == col) {
                    sb.append('Q');
                } else {
                    sb.append('.');
                }
            }
            sl.add(sb.toString());
        }
        return sl;
    }

    // 현재 위치 (row, col)에 퀸을 놓을 수 있는지 체크
    private boolean isPosable(List<List<Integer>> queens, int row, int col) {
        for (List<Integer> queen : queens) {
            if (queen.get(1) == col || // 같은 열 체크
                    queen.get(0) + queen.get(1) == row + col || // 대각선 / 체크
                    queen.get(0) - queen.get(1) == row - col)   // 대각선 \ 체크
                return false;
        }
        return true;
    }
}

4. 코드 포인트 해설

• isPosable 로직: 퀸의 공격 범위를 수학적으로 정의했습니다. 특히 대각선 체크 시 행과 열의 합과 차가 일정하다는 성질을 이용하면 $O(1)$의 수식으로 간결하게 표현할 수 있습니다.
• queens.removeLast(): 재귀 호출이 끝난 후 마지막에 추가된 요소를 제거함으로써 스택 구조처럼 현재 경로를 취소하고 이전 상태로 돌아가는 백트래킹의 핵심을 구현했습니다.
• 유연한 포맷팅: 퀸의 좌표값만 관리하다가, 정답을 찾은 순간에만 getStrings 메서드를 통해 요구하는 List<String> 형태로 변환하여 연산의 효율성을 높였습니다.

5. 성능 및 복잡도

• 시간 복잡도: 퀸을 배치할 수 있는 경우의 수는 최대 **$O(N!)$**에 비례합니다. 각 배치 시마다 isPosable 검사를 수행하므로 전체적인 탐색 속도는 $N$이 커짐에 따라 급격히 증가하지만, 문제의 범위인 $N=9$ 내외에서는 매우 빠르게 동작합니다.
• 공간 복잡도: 재귀 호출의 깊이가 $N$이며, 현재 경로의 퀸 위치를 저장하므로 **$O(N)$**의 추가 공간을 사용합니다. (결과 리스트 제외)

6. 마치며

N-Queens는 백트래킹의 교과서적인 문제로, 재귀 구조와 상태 복구라는 개념을 익히기에 최적입니다. 대각선 조건을 수식으로 처리하는 부분과 removeLast()를 통한 상태 관리 부분을 잘 기억해두면 유사한 완전 탐색 문제들을 쉽게 해결할 수 있습니다.