[Lv.2] 피로도 : Java / DFS+백트래킹

탐험 시작할 때 필요한 최소 필요 피로도

탐험 마쳤을 때 소모되는 소모 피로도

현재 피로도 k

 

import java.util.*;

class Solution {
    // 현재 피로도 k
    static int[][] dungeons; // 탐험할 수 있는 최대 던전 수 리턴하기
    
    static boolean[] used; // 던전 방문여부 저장
    static int answer = 0;
    public int solution(int k, int[][] dungeons) {
        this.dungeons = dungeons;
        used = new boolean[dungeons.length];
        
        dfs(k, 0);  // 방문한 던전 수 0
        
        return answer;
    }
    
    public static void dfs(int k, int cnt){
        answer = Math.max(answer, cnt);
        
        for(int i=0; i<dungeons.length; i++){
            int need = dungeons[i][0];  // 최소 필요 피로도
            int cost = dungeons[i][1];  // 소모 피로도
            
            if(!used[i] && k >= need){
                // 던전에 방문할 수 있는 경우
                used[i] = true;
                dfs(k-cost, cnt+1);
                used[i] = false;  
            }
        }
    }
}

 

class Solution {
    static boolean[] visited;
    static int answer = -1; // 탐험할 수 있는 최대 던전 수
    
    public int solution(int k, int[][] dungeons) {
        
        visited = new boolean[dungeons.length];
        
        dfs(0, k, dungeons);
        
        return answer;
    }
    
    static void dfs(int depth, int k, int[][] dungeons){
        answer = Math.max(answer, depth);
        
        for(int i=0; i<dungeons.length; i++){
            if(visited[i]) continue;
            if(k < dungeons[i][0]) continue;
            
            visited[i] = true;
            dfs(depth+1, k-dungeons[i][1], dungeons);
            visited[i] = false;
        }
    }
}