치킨 배달

문제

언어

  • JavaScript

순서도

  1. 집 정보와 치킨집 정보 수집
  2. 존재하는 치킨집 중에서 폐업시키지 않을 M 개의 치킨집을 고르는 모든 경우 계산
  3. 각 경우마다 도시의 치킨 거리 구하기
  4. 모든 경우의 도시의 치킨 거리 중에서 최솟값 구하기

문제 풀이 step 1

  • 크기가 N x N 인 도시가 있습니다. 도시는 1 x 1 크기의 칸으로 이루어져 있습니다.
  • 도시의 각 칸은 빈 칸 (0), 집 (1), 치킨집 (2) 중 하나입니다.
  • 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리입니다. 각각의 집은 치킨 거리를 가지고 있습니다.
  • 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다.
  • 치킨집 본사에서 수익 증가를 위해 M 개의 치킨집을 제외한 나머지 치킨집을 폐업시킬 예정입니다.
  • 이 때, 현재 있는 치킨집 중에서 도시의 치킨 거리가 최소가 되도록 M 개의 치킨집 고르고, 그 도시의 치킨 거리를 구하는 문제입니다.

문제 풀이 step 2

  • 본 문제는 완전 탐색 문제로, N 개의 치킨집 중에서 폐업시키지 않을 M 개의 치킨집을 고르는 모든 경우의 수를 계산하는 문제입니다.
  • M 개의 치킨집을 고르는 경우의 수를 계산하는 방법은 백준 15650번 - N과 M(2) 풀이 를 참고하시면 좋을 것 같습니다.
  • 각 집마다 치킨 거리를 쉽게 구하기 위해서 우선 모든 집의 정보를 수집합니다.
  • 그리고 M 개의 치킨집을 고르기 위해서 모든 치킨집의 정보도 수집합니다.

문제 풀이 step 3

  • 그 다음으로는 재귀 함수 형식으로 N 개의 치킨집에서 M 개를 고르는 모든 경우의 수를 구합니다.
  • 그리고 각 경우마다 도시의 치킨 거리를 구합니다.
  • 저는 별도로 도시의 치킨 거리를 구하는 함수를 만들었습니다.
    • 이는 아까 수집한 집의 정보와 재귀 함수를 이용해서 나온 M 개의 치킨집 정보를 이용하면 쉽게 계산할 수 있습니다.
    • 각 집마다 반복을 돌며 각 치킨집과의 거리를 구하고 그 거리의 최솟값이 치킨 거리입니다.
    • 그리고 각 집마다 구한 치킨 거리를 모두 더하면 도시의 치킨 거리를 구할 수 있습니다.
  • 그리고 각 경우마다 구한 도시의 치킨 거리 중에서 최솟값을 출력하면 정답이 됩니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 최솟값 정의
let min = Number.MAX_SAFE_INTEGER;

// 도시의 치킨 거리 구하는 함수
const getChickenStreet = (houses, chickens) => {
	let wholeStreet = 0;
	for (let i = 0; i < houses.length; i++) {
		// 각 집마다 치킨 거리 구하기
		let street = Number.MAX_SAFE_INTEGER;
		for (let j = 0; j < chickens.length; j++) {
			const distance =
				Math.abs(houses[i][0] - chickens[j][0]) +
				Math.abs(houses[i][1] - chickens[j][1]);

			street = Math.min(street, distance);
		}

		// 각 집의 치킨 거리를 모두 더해서 도시의 치킨 거리 구하기
		wholeStreet += street;
	}

	// 구한 도시의 치킨 거리 return
	return wholeStreet;
};

// N 개의 치킨집 중에서 폐업시키지 않을 M 개의 치킨집을 구하는 함수
const rec = (houses, chickens, selected, index, depth, closed) => {
	if (depth === closed) {
		// 폐업시키지 않을 M 개의 치킨집 구하기
		const newChickens = chickens.filter((v, i) => selected[i]);

		// 집 정보와 M 개의 치킨집 정보를 이용해 도시의 치킨 거리 구하기
		const wholeStreet = getChickenStreet(houses, newChickens);

		// 최솟값 갱신
		min = Math.min(min, wholeStreet);
		return;
	}

	if (index >= selected.length) return;

	selected[index] = false;
	rec(houses, chickens, selected, index + 1, depth + 1, closed);

	selected[index] = true;
	rec(houses, chickens, selected, index + 1, depth, closed);
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const arr = input.slice(1, n + 1).map((v) => v.split(" ").map(Number));

	// 집 정보와 치킨집 정보 수집
	const houses = [];
	const chickens = [];
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (arr[i][j] === 1) houses.push([i, j]);
			if (arr[i][j] === 2) chickens.push([i, j]);
		}
	}

	// 몇 개의 치킨집을 폐업시켜야 하는 지 계산
	const closed = chickens.length - m;
	// 치킨집을 하나도 폐업시키지 않아도 된다면, 현 상태의 도시의 치킨 거리 return
	if (closed === 0) return getChickenStreet(houses, chickens);

	// 폐업시켜야 하는 치킨집의 개수를 입력받아서
	// N 개의 치킨집 중에서 M 개의 치킨집을 선택하는 모든 경우의 수 계산
	const selected = Array.from({length: chickens.length}, () => true);
	rec(houses, chickens, selected, 0, 0, closed);

	return min;
};

console.log(solution(input));