[프로그래머스 알고리즘 고득점 Kit][완전탐색][Java] 피로도

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

프로그래머스

 

DFS와 백트래킹으로 가능한 모든 던전 탐험 순서를 확인한다.

visited 배열로 방문 여부를 관리하고

최소 피로도 조건을 만족하는가, 남은 피로도가 소모할 피로도보다 많은 가를 체크하고 
탐험을 진행한다.

 

호출이 끝나면 방문 상태를 되돌린다.

각 단계에서 탐험한 던전 수의 최댓값을 갱신한다.

class Solution {

    int k;
    int[][] dungeons;
    int dungeonCount;
    boolean[] visited;
    int ans;

    public int solution(int k, int[][] dungeons) {
        this.k = k;
        this.dungeons = dungeons;
        this.dungeonCount = dungeons.length;
        this.visited = new boolean[dungeonCount];

        dfs(k, 0);
        
        return ans;
    }
    
    private void dfs(int currentFatigue, int count) {
        ans = Math.max(ans, count);

        for(int i=0; i<dungeonCount; i++) {
            if(visited[i]) continue;
            
            if(dungeons[i][0] > currentFatigue) continue;
            
            if(dungeons[i][1] > currentFatigue) continue;
            
            visited[i] = true;
            dfs(currentFatigue - dungeons[i][1], count+1);
            visited[i] = false;
        }
    }
}