PROGRAMMERS_Lv2_피로도

📁 [Lv2_87946] 피로도

class Solution {
    public boolean[] check;
    public int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        
        check = new boolean[dungeons.length];
        dfs(0,k,dungeons);
        return answer;
    }
    
    public void dfs(int depth, int k, int[][] dungeons){
        for(int i=0; i<dungeons.length; i++){
            // 이미 왔는 곳이면 통과
            if(check[i]) continue;
            // 최소 필요 피로도가 없으면 통과
            if(dungeons[i][0] > k) continue;
            
            // 방문 처리
            check[i] = true;
            dfs(depth+1,k-dungeons[i][1], dungeons);
            // 백트래킹
            check[i] = false;
        }
        
        answer = Math.max(answer,depth);
    }
}

🤔 나의 생각

완전 탐색을 통해 푼 문제이다.
만약 배열의 길이가 길었다면 시간 초과가 났을 테지만 다행히 8개가 최대 개수여서 완전 탐색을 해도 시간 초과가 나지 않는다.
dfs를 이용해 방문처리를 통해 모든 배열을 돌아주며 마지막에 가장 큰 depth를 출력하면 된다.