프로그래머스 피로도(완전 탐색) - 자바스크립트 풀이

프로그래머스

 

해당 문제는 완전탐색을 이용하여 풀 수 있는 문제이다. 완전 탐색의 여러 방식 중 DFS를 이용하여 문제를 풀어보자.

function explore(e, dungeons, count)

explore라는 함수를 만들어주었다. 인자는 다음과 같다.

e: 현재 남은 피로도

dungeons: 현재 남은 던전 배열

count: 현재까지 몇 개의 던전을 돌았는지

let maxCount = count;

최대 몇 개의 던전을 돌 수 있는지 구해야하므로 maxCount라는 변수를 정의했다. 초기값은 인자로 받아온 count이다.

function explore(e, dungeons, count) {
    let maxCount = count;
    
    for(let i = 0; i < dungeons.length; i++){
        const [min, cons] = dungeons[i];
        
        if(e >= min){
            let remainDungeons = dungeons.slice(); 
            remainDungeons.splice(i,1);
            maxCount = Math.max(maxCount, explore(e - cons, remainDungeons, count + 1));
        }
    }
    return maxCount;
}

이제 explore 함수로 남은 던전을 차례대로 돌았을 때 return 되는 값을 이용해 최대 던전 방문 횟수를 구해낸다. 

function solution(k, dungeons){
    return explore(k, dungeons, 0);
}

solution함수는 다음과 같이 explore함수를 인자값 count = 0을 주고 실행시킨다.
이 때 동작을 살펴보자. 

예시로 solution(80, [[80,20],[50,40],[30,10]]) 일 때
먼저 explore(80,  [[80,20],[50,40],[30,10]], 0) 이 실행된다.

주석으로 작성된 설명을 참고해보자.

// 인자값 e =80, dungeons= [[80,20],[50,40],[30,10]] count = 0

function explore(e, dungeons, count) { 
    let maxCount = count; // count = 0이므로 maxCount의 초기값은 0이된다.
    
    for(let i = 0; i < dungeons.length; i++){ // i = 0 경우를 살펴보자.
        const [min, cons] = dungeons[i]; // [min, cons]= [80,20]이다.
        
        if(e >= min){ // 80 >= 80 은 true이다.
            let remainDungeons = dungeons.slice(); // 남은 던전을 나타내는 변수이다.
            remainDungeons.splice(i,1); // remainDungeons = [[50,40],[30,10]]이다.
            maxCount = Math.max(maxCount, explore(e - cons, remainDungeons, count + 1));
			// explore(80 - 20, [[50,40],[30,10]], 1) 값과 현재 maxCount 값 중 더 큰 값이 maxCount가 된다.
        }
    }
    return maxCount; // 이제 maxCount를 반환해주자.
}

전체 코드

function explore(e, dungeons, count) {
    let maxCount = count;
    
    for(let i = 0; i < dungeons.length; i++){
        const [min, cons] = dungeons[i];
        
        if(e >= min){
            let remainDungeons = dungeons.slice(); 
            remainDungeons.splice(i,1);
            maxCount = Math.max(maxCount, explore(e - cons, remainDungeons, count + 1));
        }
    }
    return maxCount;
}

function solution(k, dungeons){
    return explore(k, dungeons, 0);
}