이전에 파이썬으로 한번 풀어봤지만 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
}
'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 |