프로그래머스 - 피로도

 

<문제>

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

프로그래머스

 

<문제 핵심>

1. 완전 탐색

✅ dungeons배열에 있는 요소들을 차례대로 가는 것이 아닌 모든 요소들을 탐색하면서 유저가 탐험할 수 있는 최대 던전 수를 구하는 문제이다.  dfs와 백트래킹 알고리즘을 활용하여 모든 조합을 만들고 answer에 추가하여 제일 큰 숫자를 출력하면 된다. dfs 함수 로직을 짜는 과정에서 호출할 때 인자 2개를 활용하여 호출하는 것이 핵심이였다. 

 

<문제 풀이과정 및 순서도>

1. dfs(0, k)를 호출한다. 0은 count를 의미하고 k는 현재 사용자의 피로도를 의미한다.

 

2. dfs함수를 구현하는데 백트래킹 알고리즘을 활용하여 유저가 탐험할 수 있는 최대 던전 수를 구한다.

✅ 이번에는 forEach 메소드를 이용하여 solution함수 매개변수에 있는 dungeons배열을 순회하고 백 트래킹 알고리즘을 활용해봤다. 

✅ 두 번째 던전까지는 조건을 만족하는데 세 번째 던전에서 조건이 불만족되면? 다시 두 번째 던전으로 돌아가서 탐색해야 하니까 visited[index] = false를 통해 돌아갈 수 있는 환경 마련해주기

3. answer배열에서 가장 큰 요소를 구한다. -> Math.max(...answer)

 

function solution(k, dungeons) {
    let answer = [];
    let dungeonsCount = dungeons.length;
    let visited = Array(dungeonsCount).fill(false);
    //3개의 배열이 담겨져있음
    
    const dfs = (count, k) => {
        answer.push(count);
        dungeons.forEach((dungeon, index) => {
           let [minStamina, useStamina] = dungeon;
           if(k >= minStamina && !visited[index]) {
               visited[index] = true;
               dfs(count + 1, k - useStamina)
               visited[index] = false;
           } 
        });
    }
    //dfs 함수 로직에서 에러가 남
    dfs(0, k);
    return Math.max(...answer);
}