[Java] 피로도 - Lv2 프로그래머스 완전탐색 / 코딩테스트 고득점 Kit

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

프로그래머스

 

 

 

풀이

---

이제 어느정도 기본 DFS문제는 감이 온 것 같다

백트래킹으로 던전 탐사가 가능한 최대값을 구해줬다.

class Solution {
	
    static int join = 0;
	
    public int solution(int k, int[][] dungeons) {        
        boolean[] bl = new boolean[dungeons.length];
        
        dfs(dungeons, bl, 0, k, 0, 0);
        return join;
    }
    
    public void dfs(int[][] dungeons, boolean[] bl, int sum, int k, int join2, int idx){
    	for(int i=0; i<dungeons.length; i++) {
    		if(bl[i]) continue;
    		bl[i] = true;
    		if(k-sum >= dungeons[i][0]) {
    			dfs(dungeons, bl, sum+dungeons[i][1], k, join2+1, idx+1);
    		}    		
    		bl[i] = false;    		
    	}
        join = Math.max(join, join2);

    }
}