[JS] 백트래킹 with 백준

❗️ N-Queen - 백준 9663번

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

✅ backtrack 구현

const N = 4;

let tmp = [];
let count = 0;
let string = "";
function nqueen() {
  if (tmp.length === N) {
    // string에 케이스 저장
    string += tmp.join(" ") + "\n";
    count++;
    return;
  } else {
    for (let i = 1; i <= N; i++) {
      // 존재할경우 패스
      if (tmp.includes(i)) continue;

      let check = false;
      // 값의 차이와 Index의 차이의 절댓값이 같을 경우 패스
      tmp.forEach((target) => {
        let abs = Math.abs(target - i);
        let index = Math.abs(tmp.indexOf(target) - tmp.length);
        if (abs === index) {
          check = true;
        }
      });
      
      if (check) {
        continue;
      } else {
        tmp.push(i);
        nqueen();
        tmp.pop();
      }
    }
  }
}
nqueen();
console.log(count);

❗️ 연산자 끼워넣기 - 백준 14888번

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

✅ backtrack 구현

const N = 6;
const array = [1, 2, 3, 4, 5, 6];
const options = [2, 1, 1, 1];
// + - x /

const operater = [
  (a, b) => a + b,
  (a, b) => a - b,
  (a, b) => a * b,
  (a, b) => ~~(a / b),
];

let tmp = [];
let list = "";
function backtrack(array, options) {
  if (tmp.length === N - 1) {
    list += tmp.join(" ") + "\n";
    return;
  }

  for (let i = 0; i < options.length; i++) {
    if (options[i] === 0) continue;
    tmp.push(i);
    let optionsCopy = options.slice(0);
    optionsCopy[i] -= 1;
    backtrack(array, optionsCopy);
    tmp.pop();
  }
}

backtrack(array, options);
list = list.split("\n").map((el) => el.split(" ").map(Number));
list.pop();
let results = [];
list.forEach((el) => {
  let result = array.reduce((acc, cur, index) => {
    let func = operater[el[index - 1]];
    return func(acc, cur);
  });
  results.push(result);
});

console.log(Math.max(...results));
console.log(Math.min(...results));