[프로그래머스] 피로도

완전탐색문제에 도전했다!

1.현재 피로도
2.탐험전: 각 던전의 최소 필요 피로도
3.탐험후: 각 던전의 소모 피로도

위 세 값이 주어지고, 이 때 유저가 탐험할 수 있는 최대 던전 수를 return 

던전을 1->2->3 , 2->1->3 처럼 순서없이 돌 수 있다.

 

모든 던전탐방 경우의 수를 해보고, 가장 많은 던전을 돌 수 있는 경우의 수를 뽑으면 됨 !

function solution(k, dungeons) {
    let tired =[] // 방문한 던전 수
    const n = dungeons.length // 던전의 총 개수
    //각 던전 방문여부(방문: 1, 아직: 0)
    let ch = Array.from({ length: n }, () => 0); 

    function dfs(now, game){
        for (let i = 0; i < n; i++) {
     	   // 이 던전에 방문하지 않았고, 방문가능한 피로도이면
            if (ch[i] === 0 && dungeons[i][0]<=now) { 
                ch[i] = 1; //방문 처리
                // 피로도, 방문횟수 수정 후 dfs 재귀
                dfs(now - dungeons[i][1], game+1); 
                ch[i] = 0; // 다음을 위해 미방문처리
            }
        }
        //완주 후 남은 피로도가 0이상이면, 던전 방문 횟수 기록
        now >=0 && tired.push(game) 
    }
     dfs(k, 0)
    return Math.max(...tired); //최대 방문 횟수 return
}

사실 어떻게 지금 코드가 모든 경우의 수를 처리하는지 이해하지 못했다....

앗..!

지금 코드를 다시 보면서 이해했다.... 

for문을 돌면서 처음 방문 위치가 1, 2, 3으로 변경된다.

for문의 i가 1이면 그 안에서 재귀를 통해 1 > 2 > 3 / 1 > 3 > 2을 모두 방문할 수 있다.

1 > 1 > 1이 안되는 이유는 ch리스트로 방문 값을 처리해주었기 때문!

드디어 이해가 되었다..!

 

for문과 재귀가 중첩되면서 이해가 어려울 수 있지만, 여러 블로그의 설명을 통해 다들 이해하길~~! 아자아자~!