[백준] 15686 치킨 배달 - javascript

📌 문제

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

📌 풀이

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

const [n, m] = input.shift().split(' ').map(Number);
const city = input.map((line) => line.split(' ').map(Number));
const house = [];
const chicken = [];

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (city[i][j] === 1) house.push([i, j]);
    else if (city[i][j] === 2) chicken.push([i, j]);
  }
}

const getMinDistance = () => {
  let sum = 0;
  house.forEach(([hx, hy]) => {
    let min = Infinity;
    chicken.forEach((_, index) => {
      if (check[index] === true) {
        const [cx, cy] = chicken[index];
        min = Math.min(min, Math.abs(hx - cx) + Math.abs(hy - cy));
      }
    });
    sum += min;
  });
  return sum;
};

const check = new Array(chicken.length).fill(false);
let answer = Infinity;

const DFS = (idx, cnt) => {
  if (cnt === m) {
    answer = Math.min(answer, getMinDistance());
    return;
  } else {
    for (let i = idx; i < chicken.length; i++) {
      if (check[i] === true) continue;
      check[i] = true;
      DFS(i, cnt + 1);
      check[i] = false;
    }
  }
};

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

✔ 알고리즘 : 구현 ( DFS + 구현 )

✔ 좌표를 돌면서 집과 치킨집의 좌표를 각각 배열에 저장한다.

✔ DFS탐색을 통해 치킨집의 조합을 구한다. 선택된 치킨집은 check배열을 true로 선택되지 않은 치킨집은 false로 저장한다.

✔ 고른 치킨집 (cnt)가 m이 되었을 때 거리계산을 시작한다.

✔ 집들을 순회하며 가장 가까운 치킨집(check가 true인)과의 거리를 누적하여 합을 return 한다.

✔ 난이도 : 백준 기준 골드 5