[프로그래머스: 완전탐색] 피로도

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

프로그래머스

 

# DFS 코드

class Solution {
    int maxCount = 0; // 최대 탐험 수를 저장할 변수

    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length]; // 던전 방문 여부 체크 배열

        // DFS를 통해 던전 순서를 모두 탐색
        dfs(k, dungeons, visited, 0);

        return maxCount;
    }

    void dfs(int k, int[][] dungeons, boolean[] visited, int count) {
        // 탐험한 던전 수가 최대값보다 크면 갱신
        maxCount = Math.max(maxCount, count);

        // 모든 던전을 순회하며 다음 탐험할 수 있는 던전 찾기
        for (int i = 0; i < dungeons.length; i++) {
            int need = dungeons[i][0]; // 최소 필요 피로도
            int cost = dungeons[i][1]; // 소모 피로도

            // 방문하지 않았고, 피로도가 충분한 경우만 탐험 가능
            if (!visited[i] && k >= need) {
                visited[i] = true; // 방문 체크
                dfs(k - cost, dungeons, visited, count + 1); // 피로도 감소 후 탐험 계속
                visited[i] = false; // 방문 상태 복원 (다시 안 간 걸로 되돌림)
            }
        }
    }
}