[Baekjoon] 9663 - 👑N-Queen

😀문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

---

😁입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

---

😂출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

---

🤣예제

예제 입력 1 
8
예제 출력 1 
92

---

😃출처

• 문제를 만든 사람: baekjoon

---

😄알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

---

😎나의풀이

해당 문제는 일반적인 2차원 배열 탐색으론 시간초과를 막을 방도가 없다.
본인의 경우 한 열에 하나의 퀸을 놓는다는 사고방식으로 나름의 최적화를 하며 백트래킹했으나 시간 초과

해답은 N-Queen 문제의 패턴에 있다.

특정 좌표 (row, col)가 있다 가정했을 때,

• ↙ 해당 방향의 대각선 좌표 특징은 (row+col) 이 모두 같다. ex) (0,5) (1,4) (2,3)
• ↘ 해당 방향의 대각선 좌표 특징은 (row-col) 이 모두 같다. ex) (1,1) (2,2) (3,3)
  • 하지만 위 방식 대로라면, (2,3) 좌표의 해당 방향 대각선은 음수가 나올 수 있기에, 모두 num-1을 더해준 값으로 계산한다.

const input = require('fs').readFileSync('/dev/stdin').toString().trim()
const num = Number(input)
const board = Array.from({length: num}, () => Array(num).fill(false))
let result = 0
let cols = new Array(num).fill(false)
// 존재할 수 있는 모든 해당 방향의 대각선 수는 2*num-1
let diag1 = new Array(2*num-1).fill(false)
let diag2 = new Array(2*num-1).fill(false)

function isValid(row, col) {
    // diag1: 우측 대각, diag2: 좌측대각(row-col 음수가 나올 수 있으므로, num-1 추가)
    return !(cols[col] || diag1[row+col] || diag2[row-col+num-1])
}

function mineQueen(row) {
    if(row === num) {
        result++
        return
    } 
    for(let i = 0; i < num; i++) {
        if(!isValid(row, i)) continue
        board[row][i] = true
        cols[i] = true
        diag1[row+i] = true
        diag2[row-i+num-1] = true
        mineQueen(row+1)
        board[row][i] = false
        cols[i] = false
        diag1[row+i] = false
        diag2[row-i+num-1] = false
    }
}

mineQueen(0)
console.log(result)