프로그래머스: 피로도

import java.util.*;

class Solution {
    static boolean[] visited;  
    static int count = 0;  
  
    public int solution(int k, int[][] dungeons) {  
        visited = new boolean[dungeons.length];  
        dfs(0, k, dungeons);  
        return count;  
    }  
      
    private void dfs(int depth, int fatigue, int[][] dungeons){  
        for (int i = 0; i < dungeons.length; i++){  
            if (visited[i] || dungeons[i][0] > fatigue) {  
                continue;  
            }  
            visited[i] = true;  
            dfs(depth + 1, fatigue - dungeons[i][1], dungeons);  
            visited[i] = false;  
        }  
        count = Math.max(count, depth);  
    }  
    public static void main(String[] args) {
        int k = 80;
        int[][] dungeons = {{80,20}, {50,40}, {30,10}};
        Solution sol = new Solution();
        int result = sol.solution(k, dungeons);
        System.out.println(result);
        
    }
}

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

만약 아래 코드를 실행하면,

import java.util.*;

class Solution {
    static boolean[] visited;  
    static int count = 0;  
  
    public int solution(int k, int[][] dungeons) {  
        visited = new boolean[dungeons.length];  
        dfs(0, k, dungeons);  
        return count;  
    }  
      
    private void dfs(int depth, int fatigue, int[][] dungeons){  
        for (int i = 0; i < dungeons.length; i++){ 
            System.out.print("visited["+i+"] = "+visited[i]);
            if (visited[i]) {  
                System.out.println(", i: "+i+" 이미 방문.");
                continue;
            } else if (dungeons[i][0] > fatigue) {
                System.out.println(", i: "+i+" 체력 부족.");
                continue;
            }
            System.out.println();
            System.out.println("====dfs 발동 ====");
            visited[i] = true;  
            dfs(depth + 1, fatigue - dungeons[i][1], dungeons); 
            visited[i] = false;  
        }  
        System.out.println("count: "+count+" depth: "+depth);
        count = Math.max(count, depth);  
    }  
    public static void main(String[] args) {
        int k = 80;
        int[][] dungeons = {{80,20}, {50,40}, {30,10}};
        Solution sol = new Solution();
        int result = sol.solution(k, dungeons);
        System.out.println(result);
        
    }
}

visited[0] = false
====dfs 발동 ====
visited[0] = true, i: 0 이미 방문.
visited[1] = false
====dfs 발동 ====
visited[0] = true, i: 0 이미 방문.
visited[1] = true, i: 1 이미 방문.
visited[2] = false, i: 2 체력 부족.
count: 0 depth: 2
visited[2] = false
====dfs 발동 ====
visited[0] = true, i: 0 이미 방문.
visited[1] = false
====dfs 발동 ====
visited[0] = true, i: 0 이미 방문.
visited[1] = true, i: 1 이미 방문.
visited[2] = true, i: 2 이미 방문.
count: 2 depth: 3
visited[2] = true, i: 2 이미 방문.
count: 3 depth: 2
count: 3 depth: 1
visited[1] = false
====dfs 발동 ====
visited[0] = false, i: 0 체력 부족.
visited[1] = true, i: 1 이미 방문.
visited[2] = false
====dfs 발동 ====
visited[0] = false, i: 0 체력 부족.
visited[1] = true, i: 1 이미 방문.
visited[2] = true, i: 2 이미 방문.
count: 3 depth: 2
count: 3 depth: 1
visited[2] = false
====dfs 발동 ====
visited[0] = false, i: 0 체력 부족.
visited[1] = false
====dfs 발동 ====
visited[0] = false, i: 0 체력 부족.
visited[1] = true, i: 1 이미 방문.
visited[2] = true, i: 2 이미 방문.
count: 3 depth: 2
visited[2] = true, i: 2 이미 방문.
count: 3 depth: 1
count: 3 depth: 0
3