https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
📌 작성한 코드
// 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);
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 4 : 16234 - 인구 이동 (1) | 2024.02.11 |
|---|---|
| [JavaScript] 백준 골드 5 : 14891 - 톱니바퀴 (1) | 2024.02.11 |
| [JavaScript/백트래킹] 백준 실버 1 : 14889 - 스타트와 링크 (2) | 2024.02.08 |
| [JavaScript/백트래킹] 백준 골드 4 : 9663 - N-Queen (0) | 2024.02.08 |
| [JavaScript/백트래킹] 백준 실버 2 : 1182 - 부분수열의 합 (0) | 2024.02.08 |