51. N-Queens - 데일리 문제

51. N-Queens

난이도: Hard

---

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

 

Constraints:

• 1 <= n <= 9

문제 설명

간단하게 n x n 체스판이 있을 때 n 개의 퀸이 서로 공격할 수 없는 위치를 리턴하는 문제이다. 

 

우선 문제를 풀기전에 체스에서 퀸의 규칙을 알아야 합니다.

퀸은 방향 제한없이 좌우 상하 대각선 모두 움직일 수 있기 때문에 우리는 이점을 고려해서 문제를 풀어야 합니다.

 

퀸 규칙

1. 퀸은 좌우 상하 모두 이동 가능하기 때문에  각 행에서 1개만 존재할 수 있다.

 

2. 행 과 열을 이용해서 대각선 방향에 퀸이 존재하는지 체크 가능. 

 

행 - 열

 

행 + 열

 

 

코드 

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    const board = Array.from({length:n},()=>Array(n).fill('.'))
    const col = new Set()
    // 대각선
    const posDiag = new Set()
    const negDiag = new Set()
    const res = [] 
    
    function backTrack(r){
    	// r === n 이 같다는 것은 n개의 퀸을 모두 배치 했다는 것 
        if(r === n){
            res.push(board.map(row=>row.join('')))
            return 
        }
        // for문을 통해 각 행의 열을 순회
        for(let c=0; c<n; c++){
            if(col.has(c) || posDiag.has(r-c) || negDiag.has(r+c)) continue
            
            col.add(c)
            posDiag.add(r-c)
            negDiag.add(r+c)
            board[r][c] = "Q"
            
            // 다음 행 
            backTrack(r+1)
                    
            col.delete(c)
            posDiag.delete(r-c)
            negDiag.delete(r+c)
            board[r][c] = "."
        }
    }
    // 0번 인덱스 행부터
    backTrack(0)
    return res
};

 

더 자세한 설명은 아래 영상을 보면 알 수 있습니다

 

https://youtu.be/Ph95IHmRp5M