[boj] 15686. 치킨 배달 (node.js)

문제

[boj] 15686. 치킨 배달 (node.js)

• 브루트포스 + 구현문제! 재귀함수로 모든 후보군을 탐색하고, 그에 따른 값을 계산해서 최솟값을 구하면 된다.

풀이

• 값을 계산할 때는 후보군이 될 수 있는 치킨가게와, 집들 간의 거리만 계산하면 되므로 이중포문을 사용해 구할 수 있다. 처음에 BFS로 접근해서 거리를 계산하는 바람에 시간 초과가 발생했는데, 단순히 풀리는 문제였다.

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];

const solution = () => {
  const [N, M] = input();
  let chickens = [];
  let houses = [];
  const arr = [];
  for (let i = 0; i < N; i++) {
    arr[i] = input();
    arr[i].forEach((elem, idx) => {
      if (elem === 1) houses.push([i, idx]);
      else if (elem === 2) chickens.push([i, idx]);
    });
  }

  let cand = [];
  let selected = [];
  let used = [];
  rec(0, 0);

  function rec(k, startIdx) {
    if (k === M) return cand.push([...selected]);
    else {
      for (let i = startIdx; i < chickens.length; i++) {
        if (used[i]) continue;
        used[i] = 1;
        selected.push(chickens[i]);
        rec(k + 1, i);
        used[i] = 0;
        selected.splice(selected.length - 1);
      }
    }
  }

  let result = Infinity;
  for (let i = 0; i < cand.length; i++) {
    let dist = 0;
    houses.forEach(([hr, hc]) => {
      let temp = N * N;
      cand[i].forEach(([r, c]) => {
        temp = Math.min(temp, Math.abs(hr - r) + Math.abs(hc - c));
      });
      dist += temp;
    });
    result = Math.min(dist, result);
  }
  return result;
};

let _line = 0;
const input = () => stdin[_line++].split(" ").map(Number);

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  console.log(solution());
  process.exit();
});