[JS/Programmers] 87946. 피로도

💬 문제

문제 난이도: Programmers Lv.2

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946

❗️접근방법

dfs, 완전탐색

👆 코드 (통과 🎉)

let answer = 0;
function dfs(visited, N, cur, temp, k, dungeons){
    if (cur === N) return answer = Math.max(answer, temp);
    for (let i = 0; i < N; i+=1){
        if (!visited[i]){
            visited[i] = 1;
            if (k >= dungeons[i][0]){
                dfs(visited, N, cur+1, temp+1, k - dungeons[i][1], dungeons);
            }else{
                dfs(visited, N, cur+1, temp, k , dungeons);
            }
            visited[i] = 0;
        }
    }
}

function solution(k, dungeons) {
    const N = dungeons.length;
    for (let i = 0; i < N; i+=1){
        const visited = new Array(N).fill(0);
        dfs(visited, N, 0, 0, k, dungeons);
    }
    return answer;
}

구현 방법
탐험할 수 있는 던전의 횟수의 최댓값을 구하는 문제이다.
그리디가 아닌 완전 탐색으로 접근한 이유는 던전을 탐험하는 순서에 따라 결과가 달라지기 때문이다.
즉, 던전이 1,2,3이 있을 때
1 -> 2 -> 3 순서로 가면 2개 밖에 못가지면
1 -> 3 -> 2 순서로 가면 3개 모두 갈 수 있는 경우가 있기 때문이다.
따라서 모든 경우를 탐색하고자 완전 탐색 방법을 사용했다.