문제 설명

N-Queens - LeetCode

N × N 체스판에 N개의 퀸(Queen) 을 배치하는 문제입니다.
단, 퀸들은 서로 공격할 수 없어야 함 (즉, 같은 행, 같은 열, 같은 대각선에 배치되지 않아야 함).

✅ 출력 형식

  • 가능한 모든 배치를 2D 리스트 형태로 출력
  • 각 리스트는 N개의 문자열로 구성되며,
    • Q는 퀸의 위치
    • .는 빈 칸을 의미

✅ 제약 조건

  • 1 ≤ N ≤ 9
  • 백트래킹(Backtracking)을 사용하여 최적의 해를 탐색해야 함

해설

1️⃣ 브루트포스 (O(N!)) → 비효율적

  • 모든 가능한 배치를 완전 탐색하여 조건을 확인
  • N! 개의 경우의 수 발생
  • 비효율적이므로 사용하지 않음

2️⃣ 백트래킹 (Backtracking, O(N!)) [추천]

  • DFS(깊이 우선 탐색) + 가지치기(Pruning) 사용
  • 퀸을 하나씩 배치하며, 유망하지 않은 경우 즉시 백트래킹
  • O(N!)로 해결 가능하며, N이 작을 경우 빠르게 동작

✔ 배열을 사용하여 퀸 배치 유효성 검사

  • cols: 각 열에 퀸이 있는지 여부
  • diag1 (↘ 대각선): row + col 값이 같은지 여부
  • diag2 (↙ 대각선): row - col 값이 같은지 여부

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def solveNQueens(n):
    def backtrack(row):
        if row == n:  # 모든 퀸 배치 완료
            board = ["".join(row) for row in chessboard]
            result.append(board)
            return

        for col in range(n):
            if col in cols or (row + col) in diag1 or (row - col) in diag2:
                continue  # 같은 열, 같은 대각선이면 배치 불가능

            # 퀸 배치
            chessboard[row][col] = 'Q'
            cols.add(col)
            diag1.add(row + col)
            diag2.add(row - col)

            backtrack(row + 1)  # 다음 행으로 이동

            # 백트래킹 (배치 취소)
            chessboard[row][col] = '.'
            cols.remove(col)
            diag1.remove(row + col)
            diag2.remove(row - col)

    result = []
    chessboard = [["."] * n for _ in range(n)]  # 빈 체스판
    cols, diag1, diag2 = set(), set(), set()  # 열과 대각선 기록

    backtrack(0)
    return result

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

var solveNQueens = function(n) {
    let result = [];
    let chessboard = Array.from({ length: n }, () => Array(n).fill('.'));

    let cols = new Set(), diag1 = new Set(), diag2 = new Set();

    function backtrack(row) {
        if (row === n) {
            result.push(chessboard.map(row => row.join("")));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) continue;

            chessboard[row][col] = 'Q';
            cols.add(col);
            diag1.add(row + col);
            diag2.add(row - col);

            backtrack(row + 1);

            chessboard[row][col] = '.';
            cols.delete(col);
            diag1.delete(row + col);
            diag2.delete(row - col);
        }
    }

    backtrack(0);
    return result;
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform