프로그래머스 : 피로도 - javascript

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 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

 

입출력 예

k                dungeons                                  result
80              [[80,20],[50,40],[30,10]]             3

 

---

풀이과정

아이디어 1) 

 - ["최소 필요 피로도", "소모 피로도"] 중,  소모 피로도가 작은  순으로 정렬 후, 탐색 -> 실패

 

아이디어 2) 

 - ["최소 필요 피로도", "소모 피로도"] 중,   "최소 필요 피로도 - 소모 피로도"가 큰 값 순으로 정렬 후, 탐색하는 방법 -> 특정 케이스만 정답

 

아이디어 3)

DFS를 사용하여 모든 가능한 경로를 탐색하면서 최대 탐험 가능한 던전 수를 구하기

- 아직 방문하지 않은 곳이자, 현재 피로도가 최소 필요 피로도 이상인 곳 이면 더이상 방문할 수 없을 때까지 방문하기

- 방문한 곳은 더이상 방문할 수 없음 -> 성공

 

 

DFS 설명

https://kmmk808.tistory.com/46

DFS 알고리즘

 

풀이

function solution(k, dungeons) {
    let answer = 0; //최대 탐험 가능한 던전 수

    const visited=new Array(dungeons.length).fill(false);  //방문된 정보 표현

 

  function dfs(k,dungeons,count,visited){

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

       // 아직 방문하지 않은 던전이고, 현재 피로도가 해당 던전의 "최소 필요 피로도"보다 큰 경우
       if (!visited[i] && k >= dungeons[i][0]) {

            visited[i] = true;        //방문 표시
           dfs(k- dungeons[i][1], dungeons, count + 1, visited);

           visited[i] = false; // 탐험이 끝난 후 해당 던전 방문 표시 해제
      }
  }
   answer = Math.max(answer, count); //최대로 탐험 가능한 던전 수 갱신,

// answer는 최대 탐험 가능한 던전 수, count는 현재까지 탐험한 던전의 수 이므로,

// answer과 count중 큰 값을 answer에 저장 

}
   dfs(k, dungeons, 0, visited); //dfs함수 호출
   
   return answer;
}

 

 

-> 이 방법으로 하면, 모든 던전마다 두 가지 선택지(탐험하거나 탐험하지 않거나)를 모두 탐색하게 되므로 시간복잡도는 O(2ⁿ), visited라는 길이가 N인 던전의 개수만큼의 배열을 사용하므로 공간 복잡도는 O(N)

 

결과