[Baekjoon] 9663 - ๐Ÿ‘‘N-Queen

Chobbyยท2023๋…„ 11์›” 29์ผ
1

Baekjoon

๋ชฉ๋ก ๋ณด๊ธฐ
106/108

๐Ÿ˜€๋ฌธ์ œ

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)
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€