[BOJ/JavaScript] 15686: 치킨 배달

문제

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

크기가 NxN인 도시에서 도시의 치킨 거리의 최솟값을 구하라.

 

치킨 거리는 집과 가장 가까운 치킨집 사이의 거리다.

도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

치킨집을 최대 M개를 골라서 도시의 치킨 거리의 최솟값을 구해야 한다.

• 2 ≤ N ≤ 50 (집의 수는 2N개를 넘지 않는다.)
• 1 ≤ M ≤ 13

 

풀이

치킨집을 M개 골라 도시의 치킨 거리의 최솟값을 구한다.

우선 치킨집의 위치와 집의 위치를 저장해두고 M개의 치킨집을 골랐을 때, 모든 집에서의 치킨 거리를 구해 더한다. (도시의 치킨 거리)

 

처음엔 치킨 거리를 구하기 위해 막연히 최소 거리를 구하기 위해 BFS를 활용했지만 시간 초과가 발생했다. 그 이유는 최대 연산 횟수를 계산해보면,

최대 조합의 수는 M이 6이거나 7일 때 제일 크므로 13C6 = 1,716

집의 수는 2N개를 넘지 않으므로 100

BFS 연산은 격자를 모두 탐색하면 50 x 50 = 250

1,716 x 100 x 250 = 429,000,000이라는 최대 연산 횟수가 나오게 되므로 상당히 비효율적이라는 것을 알 수 있다.

💡장애물이 없는 격자에서의 최단 거리는 BFS로 계산할 필요없이 맨해튼 거리로 최단 거리를 구하면 된다.

 

코드

BFS를 활용해 풀었던 코드

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt", "utf8")
    .trim()
    .split("\n");

const [n, m] = input[0].split(" ").map(Number);
const map = input.slice(1).map(e => e.split(" ").map(Number));
const chickens = [];
const houses = [];
const dx = [1, -1, 0, 0];
const dy = [0, 0, -1, 1];

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (map[i][j] === 2) {
            chickens.push([i, j]);
        } else if (map[i][j] === 1) {
            houses.push([i, j]);
        }
    }
}

let min = Infinity;
getMin([], 0);
console.log(min);

function getMin(current, index) {
    if (current.length === m) {
        // 최소 치킨 거리 구하고 갱신
        let count = 0;
        for (let i = 0; i < houses.length; i++) {
            const [r, c] = houses[i];
            count += bfs(r, c, current);
        }
        min = Math.min(min, count);
        return;
    }

    for (let i = index; i < chickens.length; i++) {
        const chicken = chickens[i];
        current.push(chicken);
        getMin(current, i + 1);
        current.pop();
    }
}

function bfs(r, c, targets) {
    const visited = Array.from({ length : n }, () => Array(n).fill(false));
    const q = [[r, c, 0]];
    visited[r][c] = true;

    while (q.length > 0) {
        const [cr, cc, cd] = q.shift();

        for (let i = 0; i < targets.length; i++) {
            const [tr, tc] = targets[i];
            if (cr === tr && cc === tc) {
                return cd;
            }
        }
        
        for (let i = 0; i < 4; i++) {
            const nr = cr + dx[i];
            const nc = cc + dy[i];
            const nd = cd + 1;

            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (!visited[nr][nc]) {
                visited[nr][nc] = true;
                q.push([nr, nc, nd]);
            }
        }
    }
}

 

맨해튼 거리로 계산한 코드

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt", "utf8")
    .trim()
    .split("\n");

const [n, m] = input[0].split(" ").map(Number);
const map = input.slice(1).map(e => e.split(" ").map(Number));
const chickens = [];
const houses = [];

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (map[i][j] === 2) {
            chickens.push([i, j]);
        } else if (map[i][j] === 1) {
            houses.push([i, j]);
        }
    }
}

let min = Infinity;
getMin([], 0);
console.log(min);

function getMin(current, index) {
    if (current.length === m) {
        // 최소 치킨 거리 구하고 도시의 치킨 거리 갱신
        let count = 0;
        for (const [r, c] of houses) {
            count += getDist(r, c, current);
        }
        min = Math.min(min, count);
        return;
    }

    for (let i = index; i < chickens.length; i++) {
        const chicken = chickens[i];
        current.push(chicken);
        getMin(current, i + 1);
        current.pop();
    }
}

function getDist(r, c, targets) {
    let minDist = Infinity;
    for (const [tr, tc] of targets) {
        const dist = Math.abs(r - tr) + Math.abs(c - tc);
        minDist = Math.min(minDist, dist);
    }
    return minDist;
}