프로그래머스 JS [피로도]⭐⭐ visited표시남기기/순열/dfs

피로도 문제 보기

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

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

입출력 예kdungeonsresult

80

[[80,20],[50,40],[30,10]]

3

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

---

코드 설명 던전에 대해 순열을 만들어 탐색할 수 있는 모든 경우의 수를 만듭니다.    const 던전순열 = permutation(dungeons); => [   [ [ 80, 20 ], [ 50, 40 ], [ 30, 10 ] ],   [ [ 80, 20 ], [ 30, 10 ], [ 50, 40 ] ],   [ [ 50, 40 ], [ 80, 20 ], [ 30, 10 ] ],   [ [ 50, 40 ], [ 30, 10 ], [ 80, 20 ] ],   [ [ 30, 10 ], [ 50, 40 ], [ 80, 20 ] ],   [ [ 30, 10 ], [ 80, 20 ], [ 50, 40 ] ] ]  남은피로도가 필요피로도( 던전[0] )보다 많다면 던전에 입장합니다. 피로도를 필요한 요구치( 던전[1] )만큼 소모합니다.         던전탐색.forEach((던전) => {             if (남은피로도 >= 던전[0]) {                  남은피로도 -= 던전[1];                 탐험가능지역++;             }         }); 탐험가능 지역이 가장 많은 경우의 수를 반환합니다.         if (최대탐험횟수 <= 탐험가능지역) {             최대탐험횟수 = 탐험가능지역;         }     });     return 최대탐험횟수;

const permutation = (arr) => {     const result = [];     const dfs = (i, arr) => {         if (i === arr.length) {             return result.push([...arr]);         }         for (let j = i; j < arr.length; j++) {             [[arr[i]], arr[j]] = [[arr[j]], arr[i]];             dfs(i + 1, arr);             [[arr[i]], arr[j]] = [[arr[j]], arr[i]];         }     };     dfs(0, arr);     return result; }; function solution(k, dungeons) {     let 최대탐험횟수 = 0;     const 던전순열 = permutation(dungeons);     던전순열.forEach((던전탐색) => {         let 남은피로도 = k;         let 탐험가능지역 = 0;         던전탐색.forEach((던전) => {             if (남은피로도 >= 던전[0]) {                 남은피로도 -= 던전[1];                 탐험가능지역++;             }         });         if (최대탐험횟수 <= 탐험가능지역) {             최대탐험횟수 = 탐험가능지역;         }     });     return 최대탐험횟수; } solution(80, [     [80, 20],     [50, 40],     [30, 10], ]);

순열 안에서 바로 해결하는 코드 function solution(k, d) {     const N = d.length     const visited = new Array(N).fill(0)     let ans = 0     function dfs(k, cnt){         ans = Math.max(cnt, ans)         for (let j = 0; j < N; j++){             if (k >= d[j][0] && !visited[j]){                 visited[j] = 1                 dfs(k - d[j][1], cnt + 1)                 visited[j] = 0             }         }     }     dfs(k, 0)     return ans; } visited 배열을 만들어 탐색한 던전은 1을 표시합니다.     const visited = new Array(N).fill(0) 탐색이 가능하다면 1을 표시하고             if (k >= d[j][0] && !visited[j]){                 visited[j] = 1 그 다음 던전을 탐색합니다.                 dfs(k - d[j][1], cnt + 1) 다음 탐색에 영향을 주지 않도록 탐색 표시를 지웁니다.                 visited[j] = 0   탐색 횟수 중 가능 큰 수를 반환합니다.         ans = Math.max(cnt, ans)