[JavaScript] 백준 골드 5 : 15686 - 치킨 배달

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

15686번: 치킨 배달

---

📌 작성한 코드 

// 15686
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);

const chickens = [];
const board = input.map((row, i) => {
    const temp = row.split(" ");
    temp.forEach((val, j) => {
        if (val === "2") {
            chickens.push([i, j]);
        }
    });
    return temp;
});

const arr = new Array(M);
const combi = [];
const pickChicken = (at, count) => {
    if (count === M) {
        combi.push([...arr]);
        return;
    }

    for (let i = at; i < chickens.length; i++) {
        arr[count] = i;
        pickChicken(i + 1, count + 1);
    }
};


const getDistance = (x, y, stores) => {
    let min = Infinity;
    stores.forEach(([i, j]) => {
        const distance = Math.abs(x - i) + Math.abs(y - j);
        if (min > distance) min = distance;
    });

    return min;
};

pickChicken(0, 0);

let answer = Infinity;
for (let k = 0; k < combi.length; k++) {
    const current = combi[k].map((val) => chickens[val]);

    let temp = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (board[i][j] === "1") {
                temp += getDistance(i, j, current);
            }
        }
    }
    answer = Math.min(answer, temp);
}

console.log(answer);

📌 풀이 

도시에 있는 치킨집 중 M개만 남겨두고 폐업해야 한다고 했을 때, 어떻게 고르면 가장 작은 치킨거리의 합을 가지게 될지 구하는 문제이다.

치킨거리란 집에서 치킨집까지의 거리를 말한다(|r1-r2| + |c1-c2|)

 

이 문제를 풀기 위해서 구해야 하는 것들이 있다.

(1) M개의 치킨집을 선택하는 조합 구하기

(2) M개의 치킨집과 각 집에 대한 최소 거리(치킨 거리) 구하기

 

(1) M개의 치킨집을 선택하는 조합 구하기 

- 해당 조합을 구하기 위해서 백트래킹을 이용해줄 것이다. 백트래킹을 이용해서 M개의 숫자를 선택하는 로직을 작성해주고, 해당 선택된 치킨집의 번호는 `combi`에 저장해준다.

- arr를 그냥 저장하면 레퍼런스 참조라서 맨 마지막 값으로 다 저장되니꺼 복사해서 넣어줘야 한다.

const arr = new Array(M);
const combi = [];
const pickChicken = (at, count) => {
    if (count === M) {
        combi.push([...arr]);
        return;
    }

    for (let i = at; i < chickens.length; i++) {
        arr[count] = i;
        pickChicken(i + 1, count + 1);
    }
};

 

(2) 각 집에 대한 최소 거리 구하기 

- 집에 대한 최소 거리를 구하기 전에 M개의 치킨집만 남겨놨다고 생각하고 거리를 구할 것이기 때문에 (1)에서 구한 M개의 치킨집 조합을 가져와서 사용한다. 선정된 M개의 치킨집에 해당하는 좌표를 가져와서 따로 저장해준다. 

- 그리고 그 좌표들과, 집의 좌표를 가지고 최소 거리를 구해준다. 

let answer = Infinity;
for (let k = 0; k < combi.length; k++) {
    const current = combi[k].map((val) => chickens[val]);

    let temp = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (board[i][j] === "1") {
                temp += getDistance(i, j, current);
            }
        }
    }
    answer = Math.min(answer, temp);
}

- bfs를 사용해서 좌표를 구했었는데 이렇게 하면 시간 초과가 발생한다. 이 문제는 경로를 측정하는게 아니라 맨해탄 거리로 거리를 측정하기 때문에 그저 두 좌표의 차를 구하고 해당 거리 중 최솟값을 치킨거리로 설정해주면 된다.   

const getDistance = (x, y, stores) => {
    let min = Infinity;
    stores.forEach(([i, j]) => {
        const distance = Math.abs(x - i) + Math.abs(y - j);
        if (min > distance) min = distance;
    });

    return min;
};

 

// 15686
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(Number);

const chickens = [];
const board = input.map((row, i) => {
    const temp = row.split(" ");
    temp.forEach((val, j) => {
        if (val === "2") {
            chickens.push([i, j]); // 치킨집의 좌표를 chickens 배열에 저장해주기
        }
    });
    return temp;
});

const arr = new Array(M);
const combi = []; // 선택된 M개의 치킨집의 번호 조합을 저장할 배열
const pickChicken = (at, count) => {
    if (count === M) {
        combi.push([...arr]);
        return;
    }

    for (let i = at; i < chickens.length; i++) {
        arr[count] = i;
        pickChicken(i + 1, count + 1);
    }
};


const getDistance = (x, y, stores) => { // 선택된 치킨집 좌표들과 집 사이의 거리 구하기 
    let min = Infinity;
    stores.forEach(([i, j]) => { 
        const distance = Math.abs(x - i) + Math.abs(y - j); // 좌표들과 집 사이의 거리를 모두 구해보고 
        if (min > distance) min = distance; // 그 중 최솟값을 저장하기
    });

    return min;
};

pickChicken(0, 0);

let answer = Infinity;
for (let k = 0; k < combi.length; k++) {
    const current = combi[k].map((val) => chickens[val]); // 조합에서 선택된 M개의 좌표만 추출하기

    let temp = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (board[i][j] === "1") {
                temp += getDistance(i, j, current); // 전달해서 최소 거리 구하고 더해주기
            }
        }
    }
    answer = Math.min(answer, temp); // 각 조합에 따른 치킨 거리를 구하고 최솟갑이면 저장해주기 
}

console.log(answer);

 

✅ 성공