치킨 배달 | JavaScript

October 19, 2023

백트래킹백준

문제

문제를 요약하면 다음과 같습니다.

크기가 N * N인 그래프에 치킨집은 2, 집은 1, 빈 칸은 0으로 주어집니다.
치킨 거리는 집에서 치킨집까지의 거리이고, 거리는 | x1의 위치 - x2의 위치 | + | y1의 위치 - y2의 위치 | 로 구합니다.
치킨집은 그래프에 최대 M개가 올 수 있고, M개를 제외한 나머지는 모두 폐업합니다.
어떻게 고르면 치킨 거리의 합이 최소가 될지를 구합니다.

풀이

최단 거리를 구하는 문제이길래 BFS를 적용하면 되지 않을까 생각했지만, BFS를 적용해서 문제를 해결할 수 없었습니다. 여러 풀이를 참고해보고 아래와 같은 순서로 코드를 구현했습니다.

치킨집들의 위치와 집들의 위치를 각 배열에 저장합니다.
치킨집은 최대 M개만 올 수 있기 때문에, 치킨집 위치 배열에서 M개를 뽑아 조합을 만들고, 배열에 저장합니다.
- 치킨집의 순서는 중요하지 않고, 중복되어선 안되기 때문에 조합(Combination)을 만들었습니다. (nCr)
- 모든 경우의 수(중복 허용 + 순서 중요)를 고려하지 않기 때문에, 백트래킹 알고리즘이라고 할 수 있습니다.
- 이 부분 코드를 작성하는게 조금 헷갈렸는데 백준 N과 M 문제를 다시 풀어보면서 정리 할 예정입니다.
각 조합의 치킨집과 집의 거리들을 계산하고 집마다 최소 치킨거리를 구해 더한 값을 배열에 저장합니다.
배열 중 최소값을 출력합니다.

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
 
const [n, m] = input[0].split(' ').map(Number);
const graph = [];
for (let i = 1; i <= n; i++) graph.push(input[i].split(' ').map(Number));
 
// 1.
const houses = [];
const chickenHouses = [];
 
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (graph[i][j] === 1) houses.push([i, j]);
    if (graph[i][j] === 2) chickenHouses.push([i, j]);
  }
}
 
const answer = [];
 
// 2.
const combinations = [];
const visited = new Array(chickenHouses.length).fill(false);
function dfs(depth, start) {
  if (depth === m) {
    // 3.
    let total = 0;
    for (let i = 0; i < houses.length; i++) {
      let dist = 1e9;
      const [hx, hy] = houses[i];
      for (let j = 0; j < combinations.length; j++) {
        const [cx, cy] = combinations[j];
        dist = Math.min(Math.abs(hx - cx) + Math.abs(hy - cy), dist);
      }
      total += dist;
    }
 
    answer.push(total);
    return;
  }
 
  for (let i = start; i < chickenHouses.length; i++) {
    if (visited[i]) continue;
 
    combinations.push(chickenHouses[i]);
    visited[i] = true;
    dfs(depth + 1, i + 1);
    combinations.pop();
    visited[i] = false;
  }
}
 
dfs(0, 0);
 
// 4.
console.log(Math.min(...answer));