[프로그래머스] 피로도 자바 (백트래킹, dfs)

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

프로그래머스

class Solution {
    //모든 경우의 수를 다 돌아보고 아닐땐 빠져나와야함 dfs, 백트래킹
    public int answer;  //최대 던전 수 
    public boolean[] visited; //방문 여부
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        
        //dfs호출 k: 현재 피로도
        dfs(0,k,dungeons);
        
        return answer;
    
    }
    //depth : 탐험한 던전 개수
    public void dfs(int depth, int k, int[][] dungeons){
        for(int i =0; i<dungeons.length; i++){
            if(!visited[i] && dungeons[i][0] <= k){
                //방문한 적 없고, 최소필요피로도가 현재 가지고있는 피로도보다 작거나 같을 때
                visited[i] = true;
                dfs(depth+1, k- dungeons[i][1], dungeons);
                visited[i] = false; //백트래킹-> 방문 초기화
            }
        }
        
        answer = Math.max(answer, depth);
        
        
    }
    
}

 

모든 경우의 수를 탐색해야할 때 for문을 쓰려면 너무 많은 시간이 걸리고 복잡해지므로 

dfs를 사용하는 것이 좋은 방법인 것 같다!