[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

 

 

 

 

해결 방법

처음엔 무슨 규칙이 있을까 하고 이것저것 시도했지만 규칙을 찾지 못해서 실패했다.

검색해서 방법을 찾아보니 DFS를 활용하는 방법이 제일 깔끔했다.

 

1. dungeons 개수만큼 false로 채운 visited 배열을 만든다. (방문 여부 확인을 위해)

2. 모든 경우의 수를 추가할 빈 배열 result를 만든다.

3. dfs 함수의 인자로 count(몇 번 방문하고 있는지)와 k(현재 피로도)를 받는다.

4. 현재 count를 result 배열에 저장한다.

5. for문을 돌면서

  -dungeons[i][0]값이 k보다 작거나 같고 visited 배열의 해당 인덱스 값이 false 경우(방문하지 않은 경우)

    -visited 배열의 해당 인덱스를 true로 바꾼다.

    -dfs(count + 1, k - dungeons[i][1])를 호출한다.

    -호출이 다 끝나면 다음 방문을 위해 다시 visited 배열의 해당 인덱스를 false로 바꾼다.

6. result 배열에서 최댓값을 리턴한다.

 

 

 

 

전체 코드

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

 

 

 

 

 

참고 사이트

https://velog.io/@tnehd1998/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%BC%EB%A1%9C%EB%8F%84-JavaScript

[프로그래머스] 피로도 - JavaScript

 

https://velog.io/@falling_star3/2.-%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%93%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS

[Algorithm] 깊이우선탐색(DFS)과 너비우선탐색(BFS)