백준 - N-Queen(백트래킹)

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

---

배경지식

백트래킹 => 현재상태에서 가능한 모든 군을 따라들어가며 탐색하는 알고리즘

문제해결

- 문제해결방안:
1. N이 주어진다(체스판의 크기(N * N), 퀸의 개수)
2. 퀸이 놓이면 안되는 자리 판별방법으로 3가지가 있다
    ㄱ.현재 놓인 퀸과 같은 열에  있으면 안된다
    ㄴ.현재 놓인 퀸과 좌측상단, 우측하단 대각선에 있으면 안된다.(x - y 가 같음)
    ㄷ.현재 놓인 퀸과 좌측하단, 우측상단 대각선에 있으면 안된다.(x + y 가 같음)
3.현재 행(x)의 위치에서 첫번째 열부터 위의 세가지 판별방벙으로 들어갈 수 있는 곳을 판별한다.
4. x+1 다음행도 마찬가지로 판별한다.
5. N == x 같을 때 cnt를 추가해준다.
6. 행을 다 검사 했다면, 다음 열로 가기전에 판별했던 위치들을 다시 초기화 시켜 놓는다.

구현

const fs = require("fs");
const input = fs.readFileSync("dev/stdin").toString();
const N = Number(input);

let cnt = 0;
let isUsed1 = []; //ㄱ 판별방법 
let isUsed2 = []; //ㄴ 판별방법 
let isUsed3 = []; // ㄷ 판별방법 


function backtracking(x) { //x은 행을 가리킨다.
    if (x === N) {
        cnt++;
        return;
    }
    for (let i = 0; i < N; i++) {
        if (!(isUsed1[i] || isUsed2[x + i] || isUsed3[x - i + N - 1])) { //모두다 false라면, 
            isUsed1[i] = true;
            isUsed2[x + i] = true;
            isUsed3[x - i + N - 1] = true;
            backtracking(x + 1);
            isUsed1[i] = false;
            isUsed2[x + i] = false;
            isUsed3[x - i + N - 1] = false;
        }
    }
}

backtracking(0);
console.log(cnt);