프로그래머스 레벨 2 피로도 문제는 던전 목록과 HP가 주어졌을 때 방문할 수 있는 최대 던전의 수를 반환해야 한다. 각 던전은 최소 피로도와 소모 피로도를 가진다. 최소 피로도는 해당 던전을 방문하기 위해 필요한 최소 HP를 의미하고, 소모 피로도는 말 그대로 해당 던전을 방문했을 때 소모되는 HP를 나타낸다. 문제에서 주어지는 매개변수는 아래와 같다.

k : 시작 HP. e.g., 80
dungeons : [최소 피로도, 소모 피로도]로 이루어진 던전 목록. e.g., [[80,20],[50,40],[30,10]]

최소 피로도와 소모 피로도가 각각 다르기 때문에 방문 순서에 따라 방문할 수 있는 던전의 수가 달라진다. 예를들어 [[80,20],[50,40],[30,10]] 던전 목록에서 2~3번(i1~i2) 던전부터 방문하면 최대 2개 던전만 방문할 수 있다. 1번 던전(i0)의 최소 피로도가 80이기 때문에 다른 던전을 먼저 방문하면 HP가 80 미만이 되고 그럼 1번 던전의 최소 피로도를 만족하지 못하기 때문이다.

첫 번째 던전부터 방문했을 때 : 1 → 2 → 3 (최대 3개 던전)
두 번째 던전부터 방문했을 때 : 2 → 3 (최대 2개 던전)
세 번째 던전부터 방문했을 때 : 3 → 2 (최대 2개 던전)

순열을 이용한 방법

주어진 던전의 모든 가능한 순서를 탐색해봐야 하므로 던전 목록에 대한 순열(Permutation)을 생성한 뒤, 각 순열을 순회하면서 방문할 수 있는 최대 던전 개수를 계산하는 방식으로 해결했다.

const getPermutation = (arr, perm = [], max = 3) => {
  if (perm.length === max) return [perm];

  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const newPerm = [...perm, arr[i]];
    const rest = arr.slice(0, i).concat(arr.slice(i + 1));
    result.push(...getPermutation(rest, newPerm, max));
  }

  return result;
};

function solution(k, dungeons) {
  const perms = getPermutation(dungeons, [], dungeons.length);
  let maxCount = 0;

  for (const perm of perms) {
    let currentK = k;
    let count = 0;
    for (const [requiredK, consumeK] of perm) {
      if (currentK >= requiredK) {
        currentK -= consumeK;
        count++;
      } else {
        break;
      }
    }
    maxCount = Math.max(count, maxCount);
  }

  return maxCount;
}

모든 순열의 개수는 $n!$ 이므로, getPermutation 함수의 시간 복잡도는 $O(n!)$ 이 된다. solution 함수에선 생성한 순열을 다시 한 번 순회하므로 전체 코드의 시간 복잡도는 $O(n! \cdot n)$으로 비효율적이다. 만약 n이 10이라면 약 3600만 번의 연산이 필요하다.

백트래킹을 이용한 방법

<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 백트래킹, 순열은 모든 경우의 수를 탐색하여 답을 찾는 완전 탐색(Exhaustive Search)에 속한다.

</aside>

백트래킹은 문제를 해결하기 위해 가능한 모든 경우의 수를 시도하면서, 조건에 맞지 않으면 탐색을 중단하고 이전 단계로 돌아가서 다른 가능성을 탐색하는 방법이다. 깊이 우선 탐색(DFS)과 유사하지만 불필요한 경로를 배제하는 가지치기(pruning) 과정을 통해 문제를 더 효율적으로 해결한다.

프로그래머스에서 좋아요를 가장 많이 받은 코드는 백트래킹을 이용해서 해결했다. 이 문제는 순열을 고려해야 하기 때문에 시간복잡도는 최악의 경우 $O(n!)$이지만 코드가 훨씬 깔끔해진다.

function solution(k, dungeons) {
  const N = dungeons.length; // 던전 개수
  const visited = new Array(N).fill(false); // 방문 여부를 추적하는 배열
  let maxCount = 0;

  function dfs(hp, count) {
    maxCount = Math.max(count, maxCount);

    for (let i = 0; i < N; i++) {
      // 아직 방문하지 않은 던전이고, 던전의 최소 피로도를 만족하면
      if (hp >= dungeons[i][0] && !visited[i]) {
        visited[i] = true; // 방문 상태로 변경
        dfs(hp - dungeons[i][1], count + 1);
        visited[i] = false; // 미방문 상태로 변경 (백트래킹)
      }
    }
  }

  dfs(k, 0);
  return maxCount;
}