15686- 치킨 배달

링크

15686번: 치킨 배달

const [n, m] = input.shift();
const chickenCord = [];
const homeCord = [];
const final = [];
function findCord(arr, x) {
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      if (input[r][c] === x) {
        arr.push([r, c]);
      }
    }
  }
}
findCord(chickenCord, 2);
findCord(homeCord, 1);
const isUsed = new Array(chickenCord.length).fill(false);
function dfs(x = [], min = 0) {
  if (x.length === m) {
    checkDistance(x);
    return;
  }
  for (let i = min; i < chickenCord.length; i++) {
    if (!isUsed[i]) {
      isUsed[i] = true;
      dfs([...x, chickenCord[i]], i);
    }
    isUsed[i] = false;
  }
}
dfs();
function checkDistance(x) {
  let result = 0;
  for (let home of homeCord) {
    let distance = [];
    for (let chicken of x) {
      distance.push(
        Math.abs(home[0] - chicken[0]) + Math.abs(home[1] - chicken[1])
      );
    }
    result += Math.min(...distance);
  }
  final.push(result);
}
console.log(Math.min(...final));

치킨집 중에서 m개만 남겨놓고 이 m개중에서 각각의 집과의 거리를 구해서 그 합이 최소가 되는 값을 구하면 됨

1. 치킨집 중에서 m개만 남겨놓고 라는 말은 결국 좌표에 있는 모든 치킨집 중에서 m개를 고르면 됨 - dfs 함수로 구현
2. m개의 치킨집과 각 집들의 거리를 비교해야됨 - checkDistance
3. 집 한개는 여러 치킨집을 갈 수 있음 - 하지만 여기서 정의하는 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리 (이거 안읽고 한 5분 헤멤...)
4. dfs에서 m개를 골라주고, 고른 치킨집을 checkDistance 함수의 인자로 넘겨 치킨 거리를 구해주고, 최종적으로 dfs 함수가 종료하면 각 m개를 고르는 경우의 수만큼 치킨 거리가 구해지는데, 이 중 최솟값이 정답

* 그냥 일반 백트래킹을 쓰게되면 (0,1) , (1,0)이 각각 다른 값으로 인지되는데 여기서는 그럴 필요가 없기 때문에 두개를 같은 값으로 판단함