피로도

피로도

문제

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 리턴해야 함

문제의 핵심

1) DFS를 통해 모든 경로를 탐색한 후, 그에 따른 탐험 가능한 던전 수를 count해야 함.
2) 모든 count에서 최대값을 리턴한다.

예시) k = 80, dungeons = [[80, 20], [50, 40], [30, 10]]

function solution(k, dungeons) {
    
    let answer = [];
    let visited = Array(dungeons.length).fill(false);

    function dfs(count, k) {

        // answer에 count 넣어주기
        answer.push(count);

        for (let i = 0; i < dungeons.length; i++) {

            // 비교 대상인 던전에 대한 i번째 배열 설정하기
            let current = dungeons[i];
            
            // 체력 >= 최소 필요 피로도 이고 i번째 노드가 방문하지 않은 상태라면 실행하기
            if (k >= current[0] && !visited[i]) {

                // 방문 등록처리 해주기
                visited[i] = 1;

                // count에 1을 더해주고, 체력-소모피로도를 dfs에 넣어 실행하기
                dfs(count + 1, k - current[1]);

                visited[i] = 0;
            }
        }
    }

  dfs(0, k);

  return Math.max(...answer);
}

생각해 볼 문제

• 순열과 DFS에 대해 더 자세하게 공부해 볼 필요가 있음.