[프로그래머스][피로도]-Lv.2

🧨 문제

문제링크

🧨 제한사항

🧨 접근방법

1. DFS 백트래킹 방식으로 접근하였다,
2. DFS를 돌면서 count를 세가면서 최대값을 max에 저장하였다.
3. DFS가 끝났을 때 max를 반환한다.

🧨 코드

class Solution {
    static boolean[] visited;
    static int max = 0;
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        visited = new boolean[dungeons.length];
        dfs(0,0,k,dungeons);
        return max;
    }
    static void dfs(int depth, int count, int k, int[][] dungeons){
        max = Math.max(max,count);
        for(int i=0; i<dungeons.length; i++){
            if(!visited[i] && k >= dungeons[i][0]){
                visited[i] = true;
                dfs(depth+1,count+1,k-dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
    }
}