[Node.js] 15686_치킨배달

문제

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

 

풀이

이 문제는 완전탐색 문제이며 DFS를 이용해 풀이를 진행했다.

 

우선 지도에 있는 치킨집의 위치를 담고 있는 배열과 치킨집 위치 배열의 방문 여부를 표시할 배열을 생성한다.

위 두 배열을 이용해 문제에서 제공하는 제한할 치킨집의 갯수의 수 만큼 DFS로 검증한다.

 

이후 각 집 위치에서 치킨집으로 부터의 거리를 측정 후 더해준다.

 

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e.split(' ').map(Number))

const [n, h] = input.shift();
let map = input.slice();
let chicken = [];
let home = [];
let check = new Array(chicken.length).fill(false);
let answer = Infinity;


map.forEach((el, idx) => {
  el.forEach((e, i) => {
    if (e === 2) {
      chicken.push([idx, i]);
    }
  })
})

map.forEach((el, idx) => {
  el.forEach((e, i) => {
    if (e === 1) {
      home.push([idx, i]);
    }
  })
})

const dfs = (idx, cnt) => {
  if (cnt === h) {
    const sum = home.reduce((acc, [yH, xH]) => {
      let min = Infinity;
      chicken.forEach((e, i) => {
        if (check[i]) {
          const [yC, xC] = chicken[i]
          min = Math.min(min, Math.abs(yH - yC) + Math.abs(xH - xC));
        }
      })
      return acc + min;
    }, 0);
    answer = Math.min(answer, sum);
    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);