BOJ : 9663 N-Queen (JS)

소스코드

let fs = require('fs');
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

let n = Number(input[0])

let visited = []

for (let i=0 ; i < n ; i++){
    visited[i] = 0
}

let count = 0

dfs = (a) => {
    if (a === n ){
        count +=1
    }
    else {
        for(let i = 0 ; i < n ; i++){
            if (visited[a]) continue
            visited[a] = i
            if (check(a)){
                dfs(a+1)
            }
            visited[a] = 0
        }
    }
}

check = (x) => {
    for (let i = 0 ; i < x ; i++){
        if (visited[x] === visited[i]) return false
        if (Math.abs(visited[x] - visited[i]) === x-i) return false
    }
    return true
}

dfs(0)

c(count)

 

풀이

우선, 체스에서 퀸은 대각선과 위아래로 제한없이 움직일 수 없다는 점을 알아야한다.

그래서 같은 열에는 존재할 수 없고 대각선에 존재하면 되지않는다.

2차원 배열을 만들 필요없이 각 퀸이 어느 열에 위치하는지 1차원 배열을 통해 저장한 후 탐색해 모두 배치 되었을때 count를 1씩 추가해 출력을 해주면 된다.

 

문제

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

복기

https://junghyeonsu.tistory.com/194

[백준] 9663번: N-Queen (JavaScript, NodeJS)

우선 이곳의 코드를 보고 참고 했다.

대각선으로 배치했을때 어떻게 조건문을 작성할지 몰랐는데 좌표를 이용해서 뺄셈을 해주게 되면 대각선에 위치한다는 사실을 알게 되었다.

 

예를 들어 v[0] = 0 ,v[3] = 3 이면

        if (Math.abs(visited[x] - visited[i]) === x-i) return false

 

위 식을 통해 3 - 0 === 3 - 0 이므로 대각선에 위치하게 된다.