[프로그래머스] 피로도

문제 :

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

해결 :

class Solution {
    //깊이 우선 탐색(DFS)
    static int answer = 0;
    static boolean[] visited;
    static boolean flag = false;
    
    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){
        if(flag) return;
        for(int i = 0; i<dungeons.length; i++){
             //방문했거나, 피로도가 부족한 경우 continue
             if(visited[i] || k - dungeons[i][0] < 0){
                 continue;
             }
             visited[i] = true;
             dfs(depth+1, k-dungeons[i][1], dungeons);
             //방문 해제 : 해주지 않으면 첫 케이스만 진행되기 때문에. 방문 해제 필요 
             visited[i] = false;
         }
        answer = Math.max(answer, depth);
        //던전 개수만큼 다 돌았으면 실행 stop. (시간 단축)
        if(answer == dungeons.length) flag = true;
    }
}