์ด ๊ธ€์€ @longroadhome๋‹˜์˜ ๊ฒŒ์‹œ๊ธ€์„ ์ฐธ๊ณ ํ•˜์—ฌ ํ’€์ด๋œ ๊ธ€ ์ž…๋‹ˆ๋‹ค.

๐Ÿงก๋ฌธ์ œ ์„ค๋ช…

๊ฐ€๋กœ, ์„ธ๋กœ ๊ธธ์ด๊ฐ€ n์ธ ์ •์‚ฌ๊ฐํ˜•์œผ๋กœ๋œ ์ฒด์ŠคํŒ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒด์ŠคํŒ ์œ„์˜ n๊ฐœ์˜ ํ€ธ์ด ์„œ๋กœ๋ฅผ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๋„๋ก ๋ฐฐ์น˜ํ•˜๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด์„œ n์ด 4์ธ๊ฒฝ์šฐ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ€ธ์„ ๋ฐฐ์น˜ํ•˜๋ฉด n๊ฐœ์˜ ํ€ธ์€ ์„œ๋กœ๋ฅผ ํ•œ๋ฒˆ์— ๊ณต๊ฒฉ ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

์ฒด์ŠคํŒ์˜ ๊ฐ€๋กœ ์„ธ๋กœ์˜ ์„ธ๋กœ์˜ ๊ธธ์ด n์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, n๊ฐœ์˜ ํ€ธ์ด ์กฐ๊ฑด์— ๋งŒ์กฑ ํ•˜๋„๋ก ๋ฐฐ์น˜ํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ returnํ•˜๋Š” solutionํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.


๐Ÿ’›์ œํ•œ์‚ฌํ•ญ

  • ํ€ธ(Queen)์€ ๊ฐ€๋กœ, ์„ธ๋กœ, ๋Œ€๊ฐ์„ ์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • n์€ 12์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ž…๋‹ˆ๋‹ค.

๐Ÿ’š์ž…์ถœ๋ ฅ ์˜ˆ

nresult
42

๐Ÿ’™์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

  • ๋ฌธ์ œ์˜ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

๐Ÿ’œ๋‚˜์˜ ํ’€์ด

function solution(n) {
    // ์กฐ๊ฑด์— ๋งŒ์กฑํ•˜๋„๋ก ๋ฐฐ์น˜ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜
    let result = 0
    // dfs์•Œ๊ณ ๋ฆฌ์ฆ˜
    function dfs(board, row) {
        // ๋งˆ์ง€๋ง‰ ํ–‰๊นŒ์ง€ ๋„๋‹ฌํ•œ ๊ฒฝ์šฐ ๊ฒฝ์šฐ์˜ ์ˆ˜ ++
        if(row === n) result++
        else {
            for(let i = 1 ; i <= n ; i ++) {
                // ๋‹ค์Œ ํ–‰์— ์ˆ˜๋ฅผ ์ถ”๊ฐ€ํ•˜๊ณ  ์œ ํšจ๊ฐ’์ธ์ง€ ๊ฒ€์‚ฌ
                board[row+1] = i
                if(isValid(board, row+1)) dfs(board, row+1)
            }
        }
    }
    // ํ€ธ์˜ ์œ„์น˜๊ฐ€ ์œ ํšจํ•œ์ง€ ๊ฒ€์‚ฌ
    function isValid(board, row) {
        for(let i = 1 ; i < row ; i ++) {
            // ํ€ธ๋ผ๋ฆฌ ๋ฒˆํ˜ธ๊ฐ€ ๊ฒน์นœ๋‹ค๋ฉด false ๋ฐ˜ํ™˜
            if(board[i] === board[row]) return false
            // ํ€ธ๋ผ๋ฆฌ ๊ธฐ์šธ๊ธฐ๊ฐ€ ๊ฐ™๋‹ค๋ฉด ๊ฐ™์€ ๋Œ€๊ฐ์„  ๊ฒฝ๋กœ์— ์žˆ๋Š”๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— false ๋ฐ˜ํ™˜
            if(Math.abs(board[i] - board[row]) === Math.abs(i-row)) return false
        }
        return true
    }
    for(let i = 1 ; i <= n ; i ++) {
        // ํŽธ์˜๋ฅผ ์œ„ํ•ด ๋ฐฐ์—ด์„ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋„๋ก n+1์˜ ๊ธธ์ด์˜ ๋ฐฐ์—ด ์ƒ์„ฑ
        const board = new Array(n+1).fill()
        board[1] = i
        dfs(board, 1)
    }
    
    return result
}
profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

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