[JS] 백준 9663 : N-Queen - 백트래킹

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

9663번: N-Queen

 

 

📋풀이방법

1. 체스가 한행에 하나의 퀸만 들어갈 수 있다는 것을 알아야한다

2. 그리고 다음 행에 퀸을 어디에 둘지 재귀로 검사하면서 백트래킹을 이용해야한다.

3. 위 그림처럼 둘 수 없는 좌표는 뻗어나갈 수 없게 재귀를 멈춰줘야한다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let N=Number(input.shift());
let count=0;
let board=Array(15).fill(0)
function check(idx){
    for(let i=0;i<idx;i++){
        //board[idx]==board[i] : 같은 열에 위치했는지
        //idx-i==Math.abs(board[idx]-board[i]) : 같은 대각선에 위치했는지
        if(board[idx]==board[i] || idx-i==Math.abs(board[idx]-board[i])){
            return 0;
        }
    }
    return 1;
}

function DFS(idx){
    if(idx==N){
        //모든 행에 퀸을 두었다면
        count++;
        return;
    }

    else {
        for(var i=0;i<N;i++){
            board[idx]=i;
            //check함수로 백트래킹을 해 가지치기를 한다.
            if(check(idx)){
                //만약 백트래킹에 걸리지않는다면 다음 행으로 넘어가 퀸을 둔다.
                DFS(idx+1);
            }
        }
    }
} 
DFS(0);
console.log(count);

 

 

💢어려웠던 점

1. 퀸이 한 행에 하나의 퀸만 존재한다는 당연한 조건을 생각하지 못햇다.

-> 이 조건이 코드를 더간단하게 한다.

 

2. 2차원배열이아닌 1차원 배열만으로 가능하다

-> 위 조건에서 한행에는 하나의 퀸이 존재하므로 배열의 인덱스에 퀸의 열 번호를 표시하면 1차원 배열로 가능하다.

3. 현재 퀸이 위치한 행열과 다음 행에 위치한 퀸이 겹치는지 확이하는 조건을 생각하지 못했다.

 - 첫 번째 조건은 현재 두었던 퀸과 이제까지 두었던 퀸의 열값이 같으면 안된다.

 - 두 번째 조건은

  | 현재 둔 퀸의 행값 - 이제까지의 퀸의 행값 | == | 현재 둔 퀸의 열값 - 이제까지의 퀸의 열값 |