[프로그래머스] 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

---

주어진 피로도 내에서 방문 가능한 최대 던전의 수 

:조건을 만족하는 모든 경우의 수 (순열: 순서 ㅇ) 을 탐색해야 한다.

=> DFS 

 

function solution(k, dungeons) {
    let answer = 0;
    let n = dungeons.length
    const visited = Array(n).fill(false);
    
    function dfs(current, count){
        answer = Math.max(answer, count);
        for(let i = 0; i < n; i++){
            let [min, cost] = dungeons[i];
            if(!visited[i] && current >= min){
                visited[i] = true;
                dfs(current - cost, count +1);
                visited[i] = false
            }
        }
    }
    dfs(k, 0);
    return answer;
}

 

dfs(k, 0)으로 함수를 호출하고, 이후로는 재귀적으로 호출이 됨

피로도 k -> 현재 피로도 current 로 대체되어 호출

count -> +1 씩 추가하여 호출

 

visited 배열을 통해 던전의 방문 여부 확인

-> 조건이 맞으면 i번째 요소에 방문 true,

다음 단계 dfs를 호출,

-> 다시 반복문 호출 

i = 0 true이므로 패스, i = 1 false 이니까 탐색

->... 반복

모든 던전이 true 가 되면 재귀호출이 끝나고 나면 해당 던전 i 선택을 풀어준다

= 다시 다른 경로에서 선택할 수 있도록 상태 복구 (백트래킹) * i 회 진행 

 

각 호출마다 dfs를 다시 호출하므로, 트리 구조로 뻗어나간다

          시작 (피로도: 80)
         /     |     \
       A       B       C
      / \     / \     / \
     B   C   A   C   A   B
    /     \ /     \ /     \
   C       B C     A B     A

이렇게하면 모든 경우의 수를 확인할 수 있게 된다.

---

재귀 함수를 호출해서 그 다음 단계로 진행되는건 알겠는데 visited[i] = false로 만드는 부분이 언제? 이뤄지는건지? 

탐색이 종료되었을때 라는데 그게 잘 이해가 안됐다. 

아래 강의를 보고 많이 도움을 받을 수 있었다.

https://www.youtube.com/watch?v=yio6FyP1N2k

 

재귀적으로 호출되는 함수는 스택에 쌓이게 되고 각 함수가 종료되고 나면 다시 호출한 곳으로 돌아가서 그 아래 코드가 수행된다.