[Algorithm] 피로도 | 요람일지

문제설명

피로도는 전체 피로도 k, [요구 필요도, 소모 필요도]가 포함된 던전들의 2차원 배열 dungeons를 입력받아 최대한 던전을 돌 수 있는 경우 도는 던전의 갯수를 구해야 한다.

문제해결

DFS와 완전탐색이 합쳐진 이런 문제는 처음에 어떻게 접근해야 할지 아직 갈피를 못잡는다.

성공한 풀이법이다. 전달받은 던전들 중에 첫 던전 부터 마지막 던전까지 방문하는 순열을 생성한 후 방문 가능한 횟수를 저장한 후 최댓값을 반환하는 프로세스를 짰다.

function solution(k, dungeons) {
  let answer = [];
   // 방문 여부를 확인하는 배열, 초기값 X
  let visited = Array(dungeons.length).fill(false);
  // 총 피로도와 방문 횟수를 파라미터로 전달받는 재귀 함수 선언
  function dfs(k, visitedNum) {
    // 던전들의 방문 횟수를 결과값 배열에 추가한다.
    answer.push(visitedNum);
    for (let i = 0; i < dungeons.length; i++) {
      // 던전의 필요 피로도와 소모 피로도 구조분해 할당
      const [need, cost] = dungeons[i];
      // 필요 피로도가 총 필요도 이하이고 방문하지 않은 상태일 때
      if (k >= need && !visited[i]) {
        // 해당 던전의 방문을 확인하고
        visited[i] = true;
        // 피로도를 소모한 후 방문횟수를 추가하여 전달한다.
        dfs(k - cost, visitedNum + 1);
        // 재귀가 끝나면 방문 여부를 초기화
        visited[i] = false;
      }
    }
  }

  dfs(k, 0);
  return Math.max(...answer);
}