[백준/15686] 치킨 배달- JavaScript

문제분류 : 백트래킹

난이도 : 골드 5

출처 : 백준 - 치킨 배달

문제

제한사항

📌 내가 생각한 풀이

조합을 이용하여 최대 M개 까지 경우의 수를 구한다음, 완전탐색을 사용하여 거리의 합이 가장 작은 M을 구하여 거리를 리턴해주자.

let inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const getDistance = (arr1, arr2) => {
  let [x1, y1] = arr1;
  let [x2, y2] = arr2;
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};
const getCombination = (selectNum, arr) => {
  let result = [];
  if (selectNum === 1) return arr.map(d => [d]);
  arr.forEach((fixed, idx, origin) => {
    let rest = origin.slice(idx + 1);
    let combination = getCombination(selectNum - 1, rest);
    let attached = combination.map(d => [fixed, ...d]);
    result.push(...attached);
  });
  return result;
};
function solution(input) {
  let [n, m] = input[0].split(" ").map(d => parseInt(d));
  let road = [];
  let house = [];
  let chicken = [];
  for (var i = 1; i < n + 1; i++) {
    let map = input[i].split(" ").map(d => parseInt(d));
    map.forEach((data, idx) => {
      if (data === 1) {
        house.push([i - 1, idx]);
      } else if (data === 2) {
        chicken.push([i - 1, idx]);
      }
    });
  }
  let newArr = [];
  let a = 10000;
  for (var k = 1; k <= m; k++) {
    let results = getCombination(k, chicken);
    results.forEach(data => {
      let sum = 0;
      for (var z = 0; z < house.length; z++) {
        let houses = house[z];
        let min = 1000000;
        for (var j = 0; j < data.length; j++) {
          let chickens = data[j];

          let ans = getDistance(houses, chickens);
          min = Math.min(min, ans);
        }
        sum += min;
      }
      a = Math.min(a, sum);
    });
  }
  console.log(a);
}
solution(inputs);

📌 느낀점

조합을 이용하여 완전탐색을 하면 비교적 쉽게 풀리는 문제였다. 하지만 완전탐색 경우의 수를 생각하기가 조금 복잡하여 집중력있게 풀면 금방 풀린다.