[Programmers] 피로도

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

프로그래머스

문제 설명

완전 탐색 문제이며 필자는 DFS를 활용하여 해결했다. 재귀에서 가장 중요한 건 종료 조건이다. 이 문제의 종료 조건으로는 두 가지를 넣었다. 하나는 피로도가 현재 입장할 던전의 최소 피로도보다 낮을 경우이고 다른 하나는 현재 입장한 던전 개수가 총 던전 개수와 같을 경우이다. 전자의 경우는 현재까지의 던전 입장 횟수와 최댓값의 대소비교를 통해 더 큰 값을 저장한다. 후자의 경우는 모든 던전을 입장한 것이므로 최댓값을 총 던전 갯수로 저장한다.

코드

class Solution {
    private int max = 0;
    private boolean[] isVisited;
    
    public int solution(int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            isVisited = new boolean[dungeons.length];
            dfs(dungeons, i, k, 0);
        }
        
        return max;
    }
    
    private void dfs(int[][] dungeons, int idx, int fatigue, int count) {
        isVisited[idx] = true;
        
        if (fatigue < dungeons[idx][0]) {
            max = Math.max(max, count);
            return;
        }
        
        fatigue -= dungeons[idx][1];
        count += 1;
        
        if (count == dungeons.length) {
            max = dungeons.length;
            return;
        }
        
        for (int i = 0; i < dungeons.length; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                dfs(dungeons, i, fatigue, count);
                isVisited[i] = false;
            }
        }
    }
}