[JS]프로그래머스 - 피로도 (Lv.2)

function solution(k, dungeons) {
    let maxCount = 0;  
    let visited = new Array(dungeons.length).fill(false);

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

        for (let i = 0; i < dungeons.length; i++) {
            if (!visited[i] && fatigue >= dungeons[i][0]) {
                visited[i] = true;
                dfs(fatigue - dungeons[i][1], count + 1);
                visited[i] = false;
            }
        }
    }

    dfs(k, 0);
    return maxCount;
}

 

• maxCount: 탐험할 수 있는 최대 던전 개수를 저장하는 변수
• visited: 방문 여부를 저장하는 배열 (false로 초기화) 
• fatigue: 현재 남은 피로도
• count: 탐험한 던전 개수
• 모든 던전에 대해 방문 가능 여부 확인
• 방문하지 않은 던전 && 현재 피로도가 최소 요구 피로도 이상이면 방문
• 방문 후 dfs(남은 피로도, count + 1) 호출
• 백트래킹: 방문한 던전을 다시 미방문 상태로 복구
• 최대 던전 개수 갱신
• 모든 탐색이 끝나면 최댓값 반환 (maxCount)