[백준] 15686 치킨 배달 - Node.js

문제

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

문제 풀이

1. n, m의 크기가 작으므로, 완전 탐색 가능
2. 집과 치킨집만 확인하면 되므로, 그래프를 순회하며 집과 치킨집 좌표를 별도의 배열에 저장해둔다.
3. 백트래킹으로 치킨집을 M개 선택하는 모든 경우를 구한다. 선택한 치킨집은 별도의 배열에 저장한다.
4. 치킨집 M개를 모두 선택했을 때, 선택한 치킨집을 기반으로 각 집마다 치킨 거리를 계산하고, 도시의 치킨 거리를 구한다.

const fs = require("fs");
const [[n, m], ...graph] = fs.readFileSync("/dev/stdin").toString().trim().split("\n")
    .map(line => line.split(" ").map(Number));
const houses = []; // 집의 좌표 배열
const chickens = []; // 치킨 좌표 배열
const selectedChickens = []; // 선택된 치킨집
let answer = Infinity;

// 집, 치킨 좌표 저장
for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
        if (graph[r][c] === 1) houses.push([r, c]);
        if (graph[r][c] === 2) chickens.push([r, c]);        
    }
}

// 완전 탐색 수행하고 정답 출력
dfs(0, 0);
console.log(answer);

function dfs(count, startIndex) {
    // M개를 모두 선택했으면 정답 갱신 및 종료
    if (count === m) {
        answer = Math.min(answer, calculateCityChickenDist());
        return;
    }
    
    for (let i = startIndex; i < chickens.length; i++) {
        // M개를 선택할 수 없으면 종료
        if (chickens.length - i + count < m) return;
        // 백트래킹
        selectedChickens.push(chickens[i]);
        dfs(count + 1, i + 1);
        selectedChickens.pop();
    }
}

// 선택한 치킨집으로 기반으로, 도시의 치킨 거리 계산
function calculateCityChickenDist() {
    let sum = 0;
    for (const [hr, hc] of houses) {
        let dist = Infinity;
        for (const [cr, cc] of selectedChickens) {
            dist = Math.min(dist, calculateDist(hr, hc, cr, cc));
        }
        sum += dist;
    }
    
    return sum;
}

// 두 좌표 사이의 거리 계산
function calculateDist(r1, c1, r2, c2) {
    return Math.abs(r1-r2) + Math.abs(c1-c2);
}