🎲 백준 15686번 치킨 배달

📣 문제

🎨 참고
💡 1. 모든 집과 치킨집의 거리를 구하기 (집 위치에 {치킨집1 좌표 : 거리,치킨집2 좌표} 이런 식으로 저장)
2. 치킨집 조합 구하고 미리 구해놓은 거리를 사용해 최소값 구하기

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input.shift().split(" ").map(Number);
const map = input.map((el) => el.split(" ").map(Number));
const chickens = [];
const houses = [];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (map[i][j] === 1) {
      houses.push([i, j]);
      map[i][j] = {};
    } else if (map[i][j] === 2) chickens.push([i, j]);
  }
}

for (let i = 0; i < houses.length; i++) {
  for (let j = 0; j < chickens.length; j++) {
    let dis =
      Math.abs(houses[i][0] - chickens[j][0]) +
      Math.abs(houses[i][1] - chickens[j][1]);
    map[houses[i][0]][houses[i][1]][JSON.stringify(chickens[j])] = dis;
  }
}

//치킨집 조합
let result = [];
const combination = (start, arr) => {
  const visited = new Array(chickens.length).fill(false);
  if (arr.length === M) {
    let sum = 0;
    for (let i = 0; i < houses.length; i++) {
      let min = Infinity;
      for (let j = 0; j < M; j++) {
        if (min > map[houses[i][0]][houses[i][1]][JSON.stringify(arr[j])])
          min = map[houses[i][0]][houses[i][1]][JSON.stringify(arr[j])];
      }
      sum += min;
    }
    result.push(sum);
  }
  for (let i = start; i < chickens.length; i++) {
    if (!visited[i]) {
      arr.push(chickens[i]);
      visited[i] = true;
      combination(i + 1, arr);
      visited[i] = false;
      arr.pop();
    }
  }
};

combination(0, []);

console.log(Math.min(...result));