[Programmers] 광물캐기 - Javascript

INDEX

https://school.programmers.co.kr/learn/courses/30/lessons/172927#

프로그래머스

 

Solution

 

선택할 수 있는 곡괭이는 총 다이아, 철, 돌 세 가지입니다. 곡괭이들을 사용해 광물을 캘 때 최소 피로도를 구하는 문제입니다. 즉, 여러 경우의 수 중에 결과가 최소가 되는 답을 구하는 문제이기 때문에 DFS를 사용할 수 있습니다.

 

우선 피로도는 파라미터로 주어지지 않기 때문에 직접 준비해야 합니다.

const piroMap = {
  diamond: { diamond: 1, iron: 1, stone: 1 },
  iron: { diamond: 5, iron: 1, stone: 1 },
  stone: { diamond: 25, iron: 5, stone: 1 },
};

다이아 곡갱이로 다이아 광물을 캘 때의 피로도는 piroMap [diamond][diamond]가 됩니다.

 

그리고 곡갱이의 개수가 파라미터로 주어지는데 0번째는 다이아, 1번째는 철, 2번째는 돌이기 때문에 이에 대한 정의도 있어야 합니다.

const tools = Object.keys(piroMap);

 

또한 DFS에서 가장 중요하다고 볼 수 있는 포인트는 종료조건입니다. 종료조건이 올바르지 않으면 무한루프 혹은 올바르지 않은 정답이 나올 수 있기 때문에 잘 정의해야 합니다. 

 

우선 DFS 함수를 보면 다음과 같습니다.

let answer = Number.MAX_SAFE_INTEGER;
function dfs(piro = 0) {
  if (sumOfArray(picks) === 0 || minerals.length === 0) {
    //종료조건
    answer = answer < piro ? answer : piro;
    return;
  }
  for (let i = 0; i < picks.length; i++) {
    if (picks[i] !== 0) {
      //곡갱이의 개수가 남아있다면
      let piroSum = 0;
      let copyMinerals = [];
      for (let j = 0; j < 5; j++) {
        //한 곡갱이 당 광물 5개까지 캘 수 있습니다.
        const mineral = minerals.shift();
        if (!mineral) break; //더 이상 캘 광물이 없다면 반복문을 빠져나갑니다.
        piroSum += piroMap[tools[i]][mineral];
        copyMinerals.push(mineral);
      }
      picks[i] -= 1;
      piro += piroSum;
      dfs(piro); //(1)
      piro -= piroSum;
      picks[i] += 1;
      while (copyMinerals.length) {
        minerals.unshift(copyMinerals.pop());
      }
    }
  }
}
function sumOfArray(arr) {
  let sum = 0;
  arr.forEach((item) => (sum += item));
  return sum;
}

저는 곡갱이 개수의 합산이 0이 되거나 더 이상 캘 광물이 없다면 DFS를 종료하도록 했습니다. 한 가지 추가로 고려해야 할 점은 종료조건 역시 처리시간에 영향을 줄 수 있기 때문에 지금처럼 배열의 원소 개수가 3개인 경우엔 상관없지만 많은 경우엔 이렇게 배열의 합산을 구해주는 함수는 좋지 않을 수 있습니다.

 

그리고 DFS 에서 잊지 말아야 할 것은 (1)으로 표기된 부분을 보면 다음 DFS로 이동하고 돌아와서는 피로도와 곡괭이의 개수를 리필(?)해줘야 합니다. 부모 노드는 자식 노드의 영향을 받 으면 안 되기 때문입니다.

 

이게 무슨 말이냐면,

예를 들어 곡갱이가 다이아, 철, 돌 하나씩 [1, 1, 1] 주어졌다고 합시다.

우리는 곡갱이를 선택하는 순서가 피로도를 결정하기 때문에 매우 중요합니다.

첫 번째 다이아 곡괭이를 사용했다면 두 번째는 철 혹은 돌 곡괭이를 선택해야 하죠. 다이아 곡괭이가 남아있다면 다이아 곡괭이를 다시 선택할 수도 있지만 예시에서는 하나씩 주어졌기 때문에 고려하지 않습니다.

 

다이어, 철, 돌 이렇게 하나씩 선택했을 때의 피로도가 첫 번째 경우의 수입니다. 

다음 철 곡갱이를 제일 먼저 선택하는 경우의 수를 고려할 때, 이전에 어떤 순서로 곡괭이를 선택했는지 혹은 그때의 피로도는 얼만지 전혀 중요하지 않습니다. 아예 다른 경우의 수이기 때문이죠. 따라서 어떤 곡괭 이를 선택했든 다음 경우의 수를 고려할 땐 초기화해줘야 합니다. 

 

그래서 copyMinerals 라는 임시 변수를 만들어 빼줬던 광물을 DFS가 끝난 시점에 다시 채워넣어준겁니다.

 

전체코드

function solution(picks, minerals) {
  const piroMap = {
    diamond: { diamond: 1, iron: 1, stone: 1 },
    iron: { diamond: 5, iron: 1, stone: 1 },
    stone: { diamond: 25, iron: 5, stone: 1 },
  };
  const tools = Object.keys(piroMap);
  let answer = Number.MAX_SAFE_INTEGER;
  function dfs(piro = 0) {
    if (sumOfArray(picks) === 0 || minerals.length === 0) {
      answer = answer < piro ? answer : piro;
      return;
    }
    for (let i = 0; i < picks.length; i++) {
      if (picks[i] !== 0) {
        picks[i] -= 1;
        let piroSum = 0;
        let copyMinerals = [];
        for (let j = 0; j < 5; j++) {
          const mineral = minerals.shift();
          if (!mineral) break;
          piroSum += piroMap[tools[i]][mineral];
          copyMinerals.push(mineral);
        }
        piro += piroSum;
        dfs(piro);
        piro -= piroSum;
        picks[i] += 1;
        while (copyMinerals.length) {
          minerals.unshift(copyMinerals.pop());
        }
      }
    }
  }
  dfs();
  return answer;
}
function sumOfArray(arr) {
  let sum = 0;
  arr.forEach((item) => (sum += item));
  return sum;
}