Programmers / Level 2 / 피로도 / JS

< 문제 바로가기 >

프로그래머스

 

function solution(k, dungeons) {
  let visited = Array.from({ length: dungeons.length }, () => false);
  let clearedCnt = 0;

  const DFS = (k, currentCnt) => {
    clearedCnt = Math.max(currentCnt, clearedCnt);

    for(let i=0; i<dungeons.length; i+=1) {
      let [minRequiredFatigue, usedFatigue] = dungeons[i];

      // 남은 피로도가 최소 필요 피로도보다 크고 방문하지 않았다면
      if(k >= minRequiredFatigue && !visited[i]) {
        visited[i] = true;
        DFS(k - usedFatigue, currentCnt + 1);
        visited[i] = false;
      }
    }
  }

  DFS(k, 0);

  return clearedCnt;
}

const k = 80;
const dungeons = [[80, 20], [50, 40], [30, 10]];

const result = solution(k, dungeons);
console.log(result);

---

전형적인 DFS 문제였다.

다만 조금 다른점이 있다면 남은 피로도를 신경쓰면서 조건문이 하나 더 들어갔다는것이다.

 

매개변수로 남은 피로도를 받으면서 depth가 깊어질 때 마다 저장되어있는 최대 방문횟수와 현재 방문횟수중에서 최댓값을 계속 갱신해나가면 된다.