[백준15686_자바스크립트(javascript)] - 치킨 배달

🔴 문제

치킨 배달

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m], ...map] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const chickens = [];
let ans = Infinity;

// 모든 치킨 위치를 저장
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (map[i][j] === 2) chickens.push([i, j]);
  }
}

// 치킨집을 없애고 난 뒤 치킨 거리를 구해서 최소값 갱신
const getChickenDistance = (selected) => {
  const houses = [];
  const survivedChickens = [];
  let totalChickenDistance = 0;

  for (let i = 0; i < selected.length; i++) {
    map[selected[i][0]][selected[i][1]] = 0;
  }

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

  for (const [houseX, houseY] of houses) {
    let minChickenDistance = Infinity;

    for (const [chickenX, chickenY] of survivedChickens) {
      const chickenDistance = Math.abs(chickenX - houseX) + Math.abs(chickenY - houseY);
      if (chickenDistance < minChickenDistance) minChickenDistance = chickenDistance;
    }

    totalChickenDistance += minChickenDistance;
  }

  for (let i = 0; i < selected.length; i++) {
    map[selected[i][0]][selected[i][1]] = 2;
  }

  return totalChickenDistance;
};

// 백트래킹으로 치킨집 없애주기
const bt = (selected, start) => {
  // 치킨집을 chickens.length - m 만큼 없애줘야 함.
  if (selected.length === chickens.length - m) {
    const chickenDistance = getChickenDistance(selected);

    if (chickenDistance < ans) ans = chickenDistance;

    return;
  }

  for (let i = start; i < chickens.length; i++) {
    bt([...selected, chickens[i]], i + 1);
  }
};

bt([], 0);

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

간단한 구현 문제. 다음과 같은 프로세스로 구현을 해준다.
1. 치킨집을 폐업해 M개의 치킨집만 남긴다.
2. 치킨 거리를 구해준다.
3. 최소 치킨 거리를 업데이트 한다.

1. 먼저 M개의 치킨집만 남겨야 하므로 없앨 치킨집을 백트래킹으로 골라주면 된다.

   // 백트래킹으로 치킨집 없애주기
   const bt = (selected, start) => {
     if (selected.length === chickens.length - m) {
       const chickenDistance = getChickenDistance(selected);
   
       if (chickenDistance < ans) ans = chickenDistance;
   
       return;
     }
   
     for (let i = start; i < chickens.length; i++) {
       bt([...selected, chickens[i]], i + 1);
     }
   };

   없앨 치킨집은 중복으로 고를 수 없으므로 두번째 매개변수로 시작 위치를 전달해 백트래킹을 수행해준다. 치킨집을 chickens.length - m 만큼 없앴다면 치킨 거리를 구해주는 함수를 수행한다.

2. 치킨집을 없애고 난 뒤, 치킨거리를 구하고 그 치킨거리를 리턴하는 함수를 수행한다.
   이 때, 백트래킹을 고른 치킨집을 없애줘야 하므로 반복문으로 고른 치킨집 배열을 순회하면서 해당 치킨집 좌표를 0으로 변경해준다.
   다 변경되었다면 다시 맵을 순회하면서 집의 위치와, 모든 치킨집의 위치를 구해 각각 houses, survivedChickens(ㅋㅋ) 에 넣어준다.
   이제 각 집들을 순회하고 각 집에서, 모든 치킨집까지의 치킨거리를 구해 합계를 구해준다.
   치킨거리를 구했다면, 아까 바꿔놨던 치킨집 배열을 다시 치킨집으로 변경시킨 뒤, 치킨거리를 리턴한다.

3. 최소 치킨 거리를 업데이트 해준다.
   getChickenDistance()함수로 부터 리턴받은 값을 통해 최소 치킨거리를 업데이트 해주고 정답을 출력해주면 끝난다.

구현 과정이 귀찮을뿐 딱히 어려운 테크닉을 요구하지는 않는 문제였다.

🔵 Ref