[백준] 15686 치킨 배달 (Javascript)

문제

BOJ15686_치킨 배달

풀이

요구사항

모든 집부터 M개의 치킨집 까지의 거리의 총 합이 최소가 되도록 하시오.

해결방안

조건에 맞게 일일히 구현하다가 막히는 부분이 생겼다.
결국 모든 코드를 지우고 접근법부터 다르게 생각해보려고 했지만 제대로 떠오르지 않았다.
결국 다른 블로그를 참고하여 풀었다.

조합

우선 우리가 주목해야할 점은 M개의 치킨집을 남겨야 한다는 점이다. 문제에서는 최대 M개의 치킨집을 골랐을 때, 도시의 치킨거리의 최솟값을 구하라고 나와있기 때문에 M개 이하로 치킨집을 남기는 경우도 고려해야 하지 않나? 생각할 수도 있다.

하지만 N*N 공간에서 치킨집이 많으면 많을수록 도시의 치킨 거리가 작아질 가능성이 높아질 뿐, 치킨 거리가 커지진 않기 때문에 최대 M개의 치킨집을 남길 수 있다면 M개의 치킨집을 남기는 것이 최솟값을 찾기 위한 최선의 선택이다.

M개 이상의 치킨집이 있고 우리는 M개의 치킨집만 남겨야 한다. 이는 조합을 통해서 모든 치킨집 중에서 M개의 치킨집을 고르는 경우를 모두 확인할 수 있고, 이때의 경우의 수는 최대 $_{13}C_M$ 이 된다.

M개의 치킨집이 선택됐다면, 각각의 집을 i라고 했을 때 i부터 M개의 치킨집까지의 거리를 구하고, 이 중 최소 거리가 i의 치킨 거리가 된다.

'i의 치킨 거리'를 '도시의 치킨 거리'에 누적하고 또다시 다음 집(i+1)부터 M개의 치킨집까지의 거리를 구하고 여기서 최소 거리(치킨 거리)를 구한 다음 이를 도시의 치킨 거리에 누적한다.

이런식으로 모든 집을 돌면 결국 모든 집부터 M개의 치킨집 까지의 치킨 거리가 '도시의 치킨 거리'에 누적된다. 이 과정을 $_{13}C_M$ 번 반복하면 각각의 조합에 대한 '도시의 치킨 거리'를 구할 수 있고, 이 중 최솟값을 구하면 정답이 된다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
let answer = Infinity;

const chickens = [];
const house = [];
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      	if (arr[i][j] === 1) house.push([i, j]);
        if (arr[i][j] === 2) chickens.push([i, j]);
    }
}

// 치킨집 M개를 골랐을 때 도시의 치킨거리 중 가장 작은값이 정답
function caculateDist(arr) {
    let dist = 0; // 도시의 치킨 거리
    let min = Infinity; // 각각의 집의 치킨 거리
    for (const [y1, x1] of house) {
        for (const [y2, x2] of arr) {
            min = Math.min(Math.abs(y1 - y2) + Math.abs(x1 - x2), min);
        }
        dist += min;
        min = Infinity;
    }
    answer = Math.min(dist, answer);
}

function combination(cur, arr) {
    if (arr.length === M) {
        caculateDist(arr);
        return;
    }
    for (let i = cur; i < chickens.length; i++) {
        combination(i + 1, [...arr, chickens[i]]);
    }
}

combination(0, []);
console.log(answer);

주의사항

조합을 구현할 때 아래처럼 cur+1을 전달해주면 중복된 연산이 많아지므로 시간초과가 난다.

for (let i = cur; i < chickens.length; i++) {
  combination(cur + 1, [...arr, chickens[i]]);
}

따라서 cur+1 대신 i+1을 전달해줘야 한다.

for (let i = cur; i < chickens.length; i++) {
  combination(i + 1, [...arr, chickens[i]]);
}