[프로그래머스 고득점 kit - 완전탐색] - 피로도

class Solution {
    int maxCount = 0;  // 최대 던전 수 저장 변수

    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];  // 방문 여부 체크
        dfs(k, dungeons, visited, 0);  // DFS 시작
        return maxCount;
    }

    private void dfs(int k, int[][] dungeons, boolean[] visited, int count) {
        // 현재까지 탐험한 던전 수로 최대값 갱신
        maxCount = Math.max(maxCount, count);

        for (int i = 0; i < dungeons.length; i++) {
            int minRequired = dungeons[i][0];
            int consume = dungeons[i][1];

            if (!visited[i] && k >= minRequired) {
                visited[i] = true;
                dfs(k - consume, dungeons, visited, count + 1);
                visited[i] = false;  // 백트래킹
            }
        }
    }
}

• 해당 문제는 전체의 피로도가 있다면 각 던전의 (최소 피로도, 소모 피로도) 세트를 돌면서 최대한 다 돌 수 있는 수를 구한 후에 최종적으로 그것을 출력하는 것인데, 던전의 순서를 바꾸면서 찾는 것이 관건이다.
• 이 또한 앞서서 배운 백트래킹을 이용해서 dfs 를 통해 구현하였다.