백준 15686 < 치킨 배달 > JavaScript

📍문제 링크

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

15686번: 치킨 배달

 

📍알고리즘 분류

- 구현

- 브루트포스

- 백트래킹

 

📍문제 풀이

- N * N 크기의 좌표 평면에서 2인 좌표가 최소 M개, 최대 N * N - 1 개, 1 도 몇 개 주어진다.

- 1인 좌표를 모두 순회하면서 2인 좌표까지의 맨해튼 거리의 총 합이 최소가 되는 것을 도출하면 된다.

 

- 2인 좌표값이 있는 배열을 백트래킹해나가야 하고, 순서는 상관없다 (조합)

 

- 맨해튼 거리의 총 합이 최소가 되려면 당연히 각 거리가 최소이어야 한다.

- 이를 구하려면 모든 2인 좌표 중에서 백트래킹으로 M개 만큼 고른 2인 좌표를 모두 탐색해서, 이 중에서 최솟값을 구해야 할 것이다. (이래서 브루트포스 태그가 붙은건가 싶다)

 

📍의사 코드

1. 좌표 평면을 2차원 배열로 만들고 1인 좌표값들, 2인 좌표값들을 배열로 추출한다.

2. 2 좌표값 배열에서 M개를 뽑는 경우의수를 실행 (조합) -> 오름차순 깨지면 가지치기하는 백트래킹 방식으로 조합 구현

3. 갯수가 M에 도달 (추출 완료)하면 1 좌표값 배열을 순회하며 최소 거리를 골라 합을 구성

4. 이를 반복하며 최솟값인 합을 출력

 

📍코드 (JavaScript)

const [in1, ...in2] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const [N, M] = in1.split(' ').map(Number);
const map = in2.map((el) => el.split(' ').map(Number));
// 치킨집 좌표를 저장하는 배열
const chickenPos = [];
// 일반집 좌표를 저장하는 배열
const housePos = [];
// 좌표 추출
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (map[i][j] === 2) chickenPos.push([i, j]);
    if (map[i][j] === 1) housePos.push([i, j]);
  }
}

const isUsed = [];
// 조합을 저장할 배열 (계속 업데이트됨)
const comb = [];
const answer = [];
// 치킨 거리를 계산하는 함수
const distanceCheck = (x, y) => {
  return Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);
};

const recursive = (depth) => {
  if (depth === M) {
    let sumDistance = 0;
    for (let house of housePos) {
      let minDistance = Infinity;
      for (let chicken of comb) {
        minDistance = Math.min(distanceCheck(house, chicken), minDistance);
      }
      sumDistance += minDistance;
    }
    answer.push(sumDistance);
    return;
  }

  for (let i = 1; i <= chickenPos.length; i++) {
    if (!isUsed[i]) {
      // 좌표값들이 왼쪽에서 오른쪽, 위에서 아래 방향 순이 되도록
      // 오름차순을 정의하기 위해, x좌표가 y좌표보다 작도록,
      // x좌표와  y좌표가 같으면 y좌표는 x 좌표보다 작아야 함
      if (
        depth > 0 &&
        (comb[depth - 1][0] > chickenPos[i - 1][0] ||
          (comb[depth - 1][0] === chickenPos[i - 1][0] &&
            comb[depth - 1][1] > chickenPos[i - 1][1]))
      )
        continue;
      comb[depth] = chickenPos[i - 1];
      isUsed[i] = true;
      recursive(depth + 1);
      isUsed[i] = false;
    }
  }
};

recursive(0);
console.log(Math.min(...answer));

 

📍리뷰

- 첫 번째 에러 : 중복된 값 나옴

수가 아닌, 좌표값을 비교하도록 해서 가지치키 조건 변경하여 해결

- 두 번째 에러 : 테케는 맞는데 칼오답

// 반례
5 4
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2

ans: 4
내 답 : Infinity

 

최종출력값부터 거슬러올라가다보니 가지치기 조건이 또 잘못됐었음

인접한 위치에서 x, y 좌표값 같은 경우 y는 작게 수정

 

📍리팩토링

절대값을 구할 때 Math.abs() 메서드를 써서 코드를 단축

가지치기 조건없이 모든 경우를 살피는게 시간은 더 빠름 20ms 정도

하지만 가지치기 조건을 부여하는게 백트래킹이기 때문에 연습할때는 중복없도록 하자