[알고리즘 연습] 백준 15686 (치킨 배달, 자바스크립트)

문제

15686번: 치킨 배달

---

풀이

도시에 있는 치킨집 중에서 M개를 제외한 나머지 치킨집을 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성한다. 즉, 도시의 치킨 거리의 최소값을 구한다.

• map 배열을 생성할 때, 집의 위치와 치킨집의 위치를 각각 저장한다.
• 조합 알고리즘으로 M개로 이루어진 치킨집 조합을 모두 구한다.
• 치킨집 조합 중 치킨 거리의 최소값을 구한다.

소스 코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map((el) => +el);
const map = Array.from({ length: N }, () => Array(N).fill(null));
const home = [];
const store = [];
const arr = [];
const visited = Array(N * N).fill(false);
let answer = Infinity;

for (let i = 1; i <= N; i++) {
  const temp = input[i].split(" ").map((el) => +el);
  for (let j = 0; j < N; j++) {
    map[i - 1][j] = temp[j];

    if (map[i - 1][j] === 1) home.push([i - 1, j]);
    if (map[i - 1][j] === 2) store.push([i - 1, j]);
  }
}

dfs(0, 0);
console.log(answer);

function dfs(cnt, start) {
  if (cnt === M) {
    let total = 0;

    for (const [hx, hy] of home) {
      let min = Infinity;

      for (const [sx, sy] of arr) {
        const cand = Math.abs(hx - sx) + Math.abs(hy - sy);
        min = Math.min(min, cand);
      }

      total += min;
    }

    answer = Math.min(answer, total);
    return;
  }

  // 조합 알고리즘
  for (let i = start; i < store.length; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    arr.push(store[i]);
    dfs(cnt + 1, i + 1);
    visited[i] = false;
    arr.pop();
  }
}