[백준][브루트포스]치킨 배달 - node.js | javascript | gold5

문제

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

15686번: 치킨 배달

 

풀이

function solve() {
  const twoIdxList = [],
    oneIdxList = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (city[i][j] === 2) twoIdxList.push([i, j]);
      else if (city[i][j] === 1) oneIdxList.push([i, j]);
    }
  }

  function getCombination(arr, num) {
    const result = [];
    if (num === 1) return arr.map((el) => [el]);

    arr.forEach((fixed, index, origin) => {
      const rest = origin.slice(index + 1);
      const combination = getCombination(rest, num - 1);
      const attached = combination.map((el) => [fixed, ...el]);
      result.push(...attached);
    });
    return result;
  }

  function getMinDistance(chickenIdx) {
    let sum = 0;
    for (const [oneX, oneY] of oneIdxList) {
      let distance = Infinity;
      for (const [twoX, twoY] of chickenIdx) {
        distance = Math.min(
          distance,
          Math.abs(oneX - twoX) + Math.abs(oneY - twoY)
        );
      }
      sum += distance;
    }
    return sum;
  }

  const combination = getCombination(twoIdxList, m);

  let answer = Infinity;
  for (const indexs of combination) {
    answer = Math.min(answer, getMinDistance(indexs));
  }
  return answer;
}

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "백준/gold/15686/testcase.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((row) => row.split(" ").map((el) => +el));
const [n, m] = input[0];
const city = input.slice(1);
console.log(solve());

이 문제는 조합만 쓰면 쉽게 푸는 문제다.
조합으로 치킨 집(2) 중 폐업 시키지 않을 인덱스 조합들을 만들고, 집(1)에서부터 치킨 집까지의 거리를 쭉 반복문 돌려서 구하면 된다.

Math.min 으로 계속해서 최소값을 반영해주면 풀이 끝 !

 

좀 더 쉬운 풀이를 아시거나 고쳐야 할 코드가 있다면 댓글로 알려주세요 ! 😀