피로도

사용 알고리즘: 완전 탐색 dfs

사용 언어: java

 

import java.util.*;

class Solution {
    static int answer;
    static boolean[] visited ;
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        
        dfs(0, k, dungeons); //카운트, 남은 체력, 던전
        
        return answer;
    }
    
    private static void dfs(int cnt, int hp, int[][] dungeons) {
        answer = Math.max(answer, cnt);    //****    
        
        for(int i=0; i<visited.length; i++) {
            if(!visited[i]) {
                if(dungeons[i][0] <= hp) {
                    visited[i] = true;
                    dfs(cnt+1, hp-dungeons[i][1], dungeons);
                    visited[i] = false;
                }
            }
        }
    }
}

 

 

이슈:

경우에 따라 visited배열이 모두 true로 바뀌지 않는 채로, dfs를 종료해야 하는 경우가 있는데 그걸 어떻게 처리하지??

 

!!!! : 

생각해보니 max값을 구하는 거니까 그냥 dfs를 돌릴 때마다 answer를 max값으로 갱신해주면 되는 거였다!!

==> 이런 비슷한 경우에 자꾸 어떻게 처리하지?라는 생각을 하는데, 맥락을 이해하기!!!