알고리즘 연습하기 - 백트래킹, 구현

🎯 문제

🎯 접근 방법

이 문제는 백트래킹 알고리즘을 이용하는 구현에 조금 더 가까운 문제이다. 문제를 한번 쭉 읽고 어떤 데이터 값이 필요하고 어떻게 가공하면 원하는 답에 접근할 수 있는지에 대해 고민한다면 빠른 시간 내에 해결이 가능하다.

집(1)의 위치를 배열로 저장해야 한다. -> 최종적으로는 집에서부터 치킨 집까지의 거리를 구해야 하기 때문이다.
치킨집(2)의 위치를 배열로 저장해야 한다. -> 주어진 입력값에는 치킨집이 여러개 존재한다. 하지만 M개 만큼의 치킨집만 거리 계산에 이용될 수 있기 때문이다.
위에서 M개 만큼의 치킨집만 거리 계산에 이용이 된다고 했는데 그럼 M개의 치킨집을 가정하여 집에서부터의 M개의 치킨집까지의 최소 거리를 구해야 한다. -> 중복되지 않는 M개의 치킨집의 좌표를 구해야 하기 때문에 백트래킹 알고리즘을 사용한다.
M개의 치킨집이 정해졌다면 해당 치킨집에서부터 집까지의 거리를 구해 더해준다. -> 이후에 최소값이 나올 때가 정답이다.

어떤 데이터를 가공하고 분석하고 계산하는 것을 체계로 잡아놓는다면 그에 맞는 알고리즘을 사용해 충분히 해결할 수 있는 문제이다. 요즘 구현 문제가 추세이고 여기에 필요한 알고리즘을 적절히 접목시키는 것을 요구하는 것 같다. 그러기에 이런 문제가 상당히 유익하게 느껴졌다.

코드를 작성하기 전에 주석으로 어떤 기능을 설계할 지 한번 적어두는 것도 좋은 방법 중 하나인 것 같다.

🎯 해결 코드 (JS)

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input.shift().split(' ').map(Number);
let board = [];
input.forEach((value) => board.push(value.split(' ').map(Number)));

// 가정집 좌표 배열에 정리
let houseLocation = [];
for (let i = 0; i < N; i += 1) {
  for (let j = 0; j < N; j += 1) {
    if (board[i][j] === 1) houseLocation.push([i, j]);
  }
}

// 치킨집 좌표 배열에 정리
let chickenLocation = [];
for (let i = 0; i < N; i += 1) {
  for (let j = 0; j < N; j += 1) {
    if (board[i][j] === 2) chickenLocation.push([i, j]);
  }
}

// 조합을 이용하여 치킨 집 경우의 수 파악하기
let candidate = [];
function chooseCount(start) {
  if (candidate.length === M) {
    calculateDistance(candidate);
    return;
  }

  for (let i = start; i < chickenLocation.length; i += 1) {
    if (!candidate.includes(chickenLocation[i])) {
      candidate.push(chickenLocation[i]);
      chooseCount(i + 1);
      candidate.pop();
    }
  }
}

let result = [];
// 거리를 계산하여 결과 배열에 넣기
function calculateDistance(array) {
  let eachDistance = 0;
  let min = 2 * N - 2;

  for (let i = 0; i < houseLocation.length; i += 1) {
    const [X, Y] = houseLocation[i];
    for (let j = 0; j < array.length; j += 1) {
      const [X1, Y1] = array[j];
      if (Math.abs(X - X1) + Math.abs(Y - Y1) < min) min = Math.abs(X - X1) + Math.abs(Y - Y1);
    }
    eachDistance += min;
    min = 2 * N - 2;
  }
  result.push(eachDistance);
}

chooseCount(0);
console.log(Math.min(...result));

🎯 문제
🎯 접근 방법
🎯 해결 코드 (JS)