[프로그래머스] 피로도 - Java(자바)

 

문제 이해

• 완전탐색 알고리즘으로 모든 경우의 수를 돌아본다.
• DFS 방식으로 check 배열을 만들어서 내가 다녀온 던전인지를 체크하면서 던전을 탐험한다.
• 피로도가 해당 던전의 최소피로도와 같거나 높을때 해당 던전을 탐험할 수 있다.
• 던전을 탐험할때 cnt+1 을 하여 list에 담는다.
• DFS가 끝이 났을때는 list에 탐험한 던전수가 들어있으므로 max값으로 return한다.

import java.util.*;
class Solution {
    static List<Integer> list = new ArrayList();
    static boolean[] check;
    public int solution(int k, int[][] dungeons) {
        check = new boolean[dungeons.length];
        DFS(dungeons, k, 0);    
                
        return Collections.max(list);
    }
    
    public void DFS(int[][] dungeons, int k, int cnt){
        
        for(int i = 0; i<dungeons.length; i++){
            if(!check[i] && k >= dungeons[i][0]){
                check[i] = true;
                list.add(cnt+1);
                DFS(dungeons, k-dungeons[i][1], cnt+1);
                check[i] = false;
            }
        }
    }
}