[백준 15686] 치킨 배달

문제

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

풀이과정

문제를 처음 봤을 때 도시 전체에 치킨집을 m개만 놓아야 하므로 조합을 이용한 경우의 수를 따져보아야 한다는 생각은 들었으나 조합을 직접 소스코드로 구현하려고 했을 때 어려움을 겪어서 순열이나 조합에 대한 구현 방법을 다시 정리하고 풀었던 문제이다.

아이디어

도시 전체에서 치킨집을 놓을 수 있는 위치를 기억한다.
치킨집을 놓을 수 있는 갯수인 m만큼 놓아야 하므로, 치킨집을 놓을 수 있는 위치 배열을 가지고 m개만 뽑는 조합을 구한다.
구한 조합에 대해 순회하면서 특정 위치에 치킨집이 놓여져 있을 때 아래와 같은 과정으로 도시의 치킨거리를 구한다.
1. 맵 전체를 순회한다.
2. 만약 순회한 위치가 일반 집이라면, 해당 집을 기준으로 모든 치킨집과의 거리를 구해서 가장 짧은 거리를 도시의 치킨거리에 더한다.

소스코드

// 입력 처리
const INPUT_NAME = "i2.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const [n, m] = input[0].split(" ").map(e => Number(e));

// 도시 전체 데이터
const map = [];
for (let i = 1; i <= n; i++) {
  map.push(input[i].split(" ").map(e => Number(e)));
}

// 치킨집을 놓을 수 있는 위치
const chickens = [];
map.forEach((row, y) => {
  row.forEach((cell, x) => {
    if (cell === 2) chickens.push([y, x])
  });
});

// 도시에 치킨 집을 m개 만큼 놓는 경우의 수 (조합)
const cases = combination(chickens);
function combination(arr) {
  const result = [];
  let temp = [];

  const DFS = (depth, begin) => {
    if (depth === m) {
      result.push(JSON.parse(JSON.stringify(temp)));
      return;
    }

    for (let i = begin; i < arr.length; i++) {
      temp[depth] = arr[i];
      DFS(depth + 1, i + 1);
    }
  };

  DFS(0, 0);
  return result;
}

// 치킨 집이 chickens 의 좌표들에 설치되어 있다고 할 때 도시의 치킨 거리를 반환함
function getTownChickenDistance(chickens) {
  let sum = 0;

  // 모든 집을 순회하면서 가장 가까운 치킨거리를 구해서 sum 값에 더함
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (map[i][j] !== 1) continue; // 일반 집이 아니면 스킵

      // 모든 치킨 집을 순회하면서 해당 집과의 치킨 거리가 가장 짧은 값을 구함
      let distance = chickens.reduce((distance, [y, x]) =>
        Math.min(
          distance,
          Math.abs(i - y) + Math.abs(j - x)
        ),
      Number.MAX_SAFE_INTEGER);

      sum += distance; // 가장 짧은 치킨거리를 도시 전체 치킨거리에 더함
    }
  }

  return sum;
}

// 문제
function solution() {

  // 치킨집을 설치하는 모든 경우의 수에 따라서 도시의 치킨 거리가 가장 낮은 값을 찾는다.
  const result = cases.reduce((distance, chickens) =>
    Math.min(
      distance,
      getTownChickenDistance(chickens)
    ),
  Number.MAX_SAFE_INTEGER);

  console.log(result);
}

// 실행
solution();