[프로그래머스] 피로도, java

- 문제

프로그래머스

- 풀이

//오랜만에 풀어 본 완전탐색 문제입니다.
//이번 문제는 DFS(깊이우선 탐색)를 이용하는 문제였습니다.

class Solution {
    //전역적으로 이용할 법한 변수와 데이터를 static으로 선언하여 주었습니다.
    static int len;
    static int result;
    static int[][] dg;
    
    public int solution(int k, int[][] dungeons) {
        
        //static으로 선언된 변수들을 채워줍니다.
        result = 0;
        len = dungeons.length;
        dg = dungeons;
        
        //for를 통해 모든 던전에서 시작하는 경우의 수를 확인해줍니다.
        for(int i=0; i<len; i++){
            //각 던전의 탐험 여부를 파악하기 위한 boolean 배열입니다.
            boolean[] check = new boolean[len];
            
            //첫번째 탐험이더라도 피로도가 부족할 수 있기 때문에 확인을 해줍니다.
            if(dg[i][0]<=k){
                check[i] = true;    //해당 탐험을 다시 반복하지 않기 위해 check에 true로 체크해줍니다.
                dfs(k-dg[i][1], 1, check);   //dfs함수를 이용해 확인합니다.
                check[i] = false;   //다음 탐색을 위해 false로 풀어줍니다.
            }
            
        }
        return result;
    }
    
    //이 문제의 풀이에 핵심이 되는 dfs 함수입니다.
    //현재까지의 탐험에 남은 피로도 nowK
    //현재까지 해낸 탐험의 수 cnt
    //현재까지 어떤 던전을 탐험했는지 기록할 check를 받아줍니다.
    static void dfs(int nowK, int cnt, boolean[] check){
        
        //이번 dfs까지 왔을 경우 몇개의 던전을 탐험했는지 result와 비교하여 result보다 클 경우
        //최대 값을 갱신해줍니다. 이 값이 답안이 됩니다.
        result = Math.max(cnt, result);
        
        //for 반복을 통해 dfs 함수로 깊이 들어갑니다.
        for(int i=0; i<len; i++){
            //check를 이용해 아직 탐험하지 않은 던전만 확인합니다.
            if(!check[i]){
                //만약 이번 던전이 아직 탐험하지 않았고, 최소 필요 피로도를 중족한다면 탐험을 진행합니다.
                if(dg[i][0]<=nowK){
                    check[i] = true;    //해당 탐험을 다시 반복하지 않기 위해 check에 true로 체크해줍니다.
                    dfs(nowK-dg[i][1], cnt+1, check); //소모 피로도를 계산해주고, 탐험 갯수, 탐험 던전을 조정해준 뒤 다음 탐색을 이어갑니다.
                    check[i] = false;   //다음 탐색을 위해 false로 풀어줍니다.
                }
            }
        }
    }
}