[JavaScript] 15686 치킨 배달 (JS)

치킨 배달

📚 문제 설명

N * N 의 크기의 도시에 치킨집이 M개 이상 있다.
그런데 M 개의 치킨집만 남기고 나머지는 다 없애려고 한다.
이 때 도시에 있는 집에서 치킨집까지의 거리의 합이 최소가 되게하면 몇인지 구하여라.

예를 들어.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

위의 도시에서 M이 2이면,
0행부터 계산했을 때, 각각의 집에서 치킨집까지의 거리는
2 + 2 + 2 + 2 + 1 + 1
으로 총 거리의 합은 10이 된다.

👨🏻‍💻 풀이 과정

도시 정보를 MAP 배열에 저장을 한 후에 도시에 있는 치킨집들 중에 M 개를 뽑는 모든 조합을 다 계산하기로 했다.
따라서 전체적인 로직은

• M 개의 치킨집을 고르는 Combination 함수로 모든 조합을 찾아서 ChickenCombination 변수에 저장.
• ChickenCombination 에 있는 각각의 값에 대해 거리를 계산, 최소 값을 저장.
• 찾아준 최소값을 리턴.
  으로 구성했다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const [N, M] = input.shift().split(' ').map(Number);
    const MAP = input.map(v => v.split(' ').map(Number));

    let ChickenArr = [];
	// 치킨 집 위치 저장.
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (MAP[i][j] === 2) {
                ChickenArr.push([i, j]);
            }
        }
    }
	// 치킨집을 M 개 고를 수 있는 모든 조합 저장.
    let ChickenCombination = [];
	// 조합 함수. 재귀를 통해 구현.
    const Combination = (Arr, index) => {
        if (Arr.length === M) {
            ChickenCombination.push(Arr);
            return;
        }
		// 하나씩 찾아가며, 재귀 진행.
        for (let i = index; i < ChickenArr.length; i++) {
            Arr.push(ChickenArr[i]);
            Combination([...Arr], i + 1);
            Arr.pop();
        }
    };
	// 조합 함수 실행.
    Combination([], 0);
	// 현재 위치와 치킨 집 위치를 주면, 최소 거리를 찾아줌.
    const Distance = (x, y, chickenHouse) => {
        let distanceArr = [];
      	// 모든 치킨 집으로 부터의 거리를 구해줌.
        for (const chickenHouseElement of chickenHouse) {
            distanceArr.push(Math.abs(x - chickenHouseElement[0]) + Math.abs(y - chickenHouseElement[1]));
        }
      	// 가장 가까운 치킨집과의 거리.
        return Math.min(...distanceArr);
    };
	// 거리 총합 계산 함수.
    const Calculate = (chickenHouse) => {
        let answer = 0;
      	// 전체 맵을 돌며 집을 확인.
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < N; j++) {
              	// 집부터 치킨집까지의 거리를 계산 후, answer 에 더해줌.
                if (MAP[i][j] === 1) {
                    answer += Distance(i, j, chickenHouse);
                }
            }
        }
        return answer;
    };

    const solution = () => {
        let min = Number.MAX_SAFE_INTEGER;
      	// 모든 조합에 대해 거리를 계산.
        for (const chickenCombinationElement of ChickenCombination) {
            let totalDistance = Calculate(chickenCombinationElement);
          	// 최소값 갱신.
            if (min > totalDistance) min = totalDistance;
        }
        console.log(min);
    };
    solution();

🧐 후기

조합을 이용하는 문제였는데, 반복문을 너무 많이 사용하여, 시간 초과가 날 것을 우려했으니 시간초과 없지 무사히 잘 통과하였다.
그래도 혹시나 해서 다른 사람들의 시간을 확인했는데, 나랑 비슷한 것까지 확인한 후에야 안심할 수 있었던 문제였다.