a-079-n-queens2026-08-06hardleetcode #51neetcode150

N-퀸 문제

#array#backtracking#algorithm-x

문제

· problem

P.a-079-n-queens

N-퀸 문제

n×n 체스판에 n개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다. 퀸은 같은 행, 열, 대각선 위치에 있는 다른 기물을 공격할 수 있습니다. 정수 n이 주어졌을 때, n-퀸 문제의 모든 서로 다른 해결책을 반환하세요. 답은 어떤 순서로든 반환할 수 있습니다. 각 해결책은 퀸을 배치한 보드 설정을 나타내며, 'Q'는 퀸을, '.'는 빈 칸을 나타냅니다.

제약

· 1 ≤ n ≤ 9
· Queens attack horizontally, vertically, and diagonally
· Each row and column can contain at most one queen

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[["..Q.","Q...","...Q",".Q.."],["Q...","...Q",".Q..","..Q."]]

example 2input → output

[["Q"]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
체스판에서 퀸이 다른 퀸을 '공격'한다는 것은 무엇을 의미하나요?
☐
같은 행에 여러 개의 퀸을 배치할 수 있나요?
☐
왜 충돌 추적을 위해 집합(set)을 사용하나요?
☐
대각선 충돌을 어떻게 표현하나요?
☐
해의 순서가 정렬되어야 하나요?
☐
백트래킹에서 상태를 복원하는 이유는?
☐
동적 계획법으로 이 문제를 해결할 수 있나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 초기화: 열 충돌 추적

○

col = set()

○

col = []

○

col = {}

step 2· 초기화: 정 대각선 충돌 추적 (r+c)

○

posDiag = set()  # (r + c)

○

posDiag = {}

○

posDiag = set()  # (r * c)

step 3· 초기화: 역 대각선 충돌 추적 (r-c)

○

negDiag = set()  # (r - c)

○

negDiag = set()  # (c - r)

○

negDiag = set()  # (r - c) % n

step 4· 기저 사례: 모든 퀸 배치 완료│ 중첩

○

if r == n:

○

if r == n - 1:

○

if len(col) == n:

step 5· 충돌 검사: 열과 대각선 확인│ │ 중첩

○

if c in col or (r + c) in posDiag or (r - c) in negDiag:

○

if c not in col and (r + c) not in posDiag and (r - c) not in negDiag:

○

if c in col or (r + c) in posDiag:

step 6· 퀸 배치 및 상태 업데이트│ │ 중첩

○

col.add(c)

○

col.add(c); posDiag.add(r + c); negDiag.add(r - c)

○

board[r][c] = "Q"

step 7· 재귀 호출: 다음 행으로 진행│ │ 중첩

○

backtrack(r + 1)

○

backtrack(r)

○

backtrack(r + 2)

step 8· 백트래킹: 상태 복원│ │ 중첩

○

col.remove(c)

○

# 백트래킹 코드 생략

○

col.clear(); posDiag.clear(); negDiag.clear()

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def solveNQueens(self, n: int) -> List[List[str]]:

        col = set()

        posDiag = set()  # (r + c)

        negDiag = set()  # (r - c)

        res = []

        board = [["."] * n for i in range(n)]

        def backtrack(r):

            if r == n:

                copy = ["".join(row) for row in board]

                res.append(copy)

                return

            for c in range(n):

                if c in col or (r + c) in posDiag or (r - c) in negDiag:

                    continue

                col.add(c)

                posDiag.add(r + c)

                negDiag.add(r - c)

                board[r][c] = "Q"

                backtrack(r + 1)

                col.remove(c)

                posDiag.remove(r + c)

                negDiag.remove(r - c)

                board[r][c] = "."

        backtrack(0)

        return res

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

→

[["..Q.","Q...","...Q",".Q.."],["Q...","...Q",".Q..","..Q."]]

case 2

→

[["Q"]]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.