[JS] N-Queen
FrontEnd/프로그래머스

[JS] N-Queen

728x90

이전에 파이썬으로 한번 풀어봤지만 JS로 오랜만에 다시만난 문제다.

 

 

먼저 N-Queen의 문제를 보면 결국 퀸은 세로줄이든 가로줄이든 하나씩밖에 못 둔다는것을 확인할 수 있다.

 

 

따라서 2차원 배열로 보드를 관리하는것이 아닌 1차원으로 관리할 수 있다.

 

 

예를들어서

 

 

[-1,-1,-1,-1]  왼쪽과 같이 처음을 배치하고 idx값을 세로줄이라고 생각해보자.

 

 

 

문제에서 정답으로 주어진 위상태를 1차원 배열로 표현한다면

 

[1,3,0,2] 가 되는것이다.

 

 

따라서 dfs를 활용해서 첫칸부터 채우는 문제로 바뀌게 된다.

 

 

dfs를 통해서 퀸을 배치할때 세로줄은 위 방법으로 해결했다. 가로줄은 위 배열을 채우면서 같은 값이 나오지 않게 하면 해결할 수 있다.

 

 

만약 [1,2,2,3] 이렇게 중복된 값이 있다면 가로줄에서 곂치는 것이므로 이를 피해줘야한다.

 

 

 

이제 마지막으로 생각할 것은 대각선이다.

 

 

 

그런데 우리가 생각할 점이 있다.

 

 

우리는 배열을 앞에서부터 채울 것이다. 즉 세로줄 기준으로 1번째부터 채워나가므로 퀸을 배치할때 내가 지금까지 배치한 퀸들 즉 내가 배치할 퀸 라인의 윗부분만 체크하면된다.

 

대각선은 네 방향이지만 위쪽 대각선 2개만 체크하면 된다는 것이다.

 

 

근데 이것도 생각해보니 수식 하나로 할만했다.

 

 

퀸의 좌표 (x,y)와 내 좌표 (a,b)가 있다고 생각하면 

 

각 x와 y좌표의 차를 계산한 이후 해당값들의 절대값이 같다면 대각선상에 있는 것이다.

 

 

이를 활용해서 퀸을 배치해가면서 수를 세 주었다.

 

 

 

 

 

 

 

 

function solution(n) {
    const board = new Array(n).fill(-1)
    let ret = 0
    
    const canCollocate = (board,col,row) => {
        
        for (let i = 0 ; i < col ; i++) {
            if (board[i]===row) return false
            if (Math.abs(col-i) === Math.abs(row - board[i])) return false
        }
        return true
    }
    
    const dfs = (col,board) => {
        
        const tmpBoard = [...board]
        if (col === n) ret ++
        
        
        for (let row = 0 ; row < n ; row++){
            
            if (canCollocate(tmpBoard,col,row)) {
                tmpBoard[col] = row
                dfs(col+1,[...tmpBoard])
            }
        }
    }

   
    dfs(0,board)
        
    return ret
    
}
728x90

'FrontEnd > 프로그래머스' 카테고리의 다른 글

[JS] 더 맵게!  (0) 2023.07.27
[JS] 하노이의 탑  (0) 2023.07.22
[JS] N개의 최소공배수  (0) 2023.07.21
[JS] 배달  (0) 2023.07.19
[JS] 짝지어 제거하기  (0) 2023.07.18