[JAVA 문제 풀이] 309. 피로도

내가 작성한 코드

class Solution {
    public int solution(int k, int[][] dungeons) {
        // 각 던전의 방문 여부를 저장하는 배열
        boolean[] visited = new boolean[dungeons.length];

        // DFS 탐색을 시작하고 최대 던전 탐험 수를 반환
        return dfs(k, dungeons, visited, 0);
    }

    // 깊이 우선 탐색(DFS) 메서드 >> 가장 많은 수의 던전을 탐험할 수 있는 경로를 찾기 위한 재귀 함수
    private int dfs(int k, int[][] dungeons, boolean[] visited, int count) {
        int maxCount = count;  // 현재까지 탐험한 던전 수를 최대값으로 초기화

        // 모든 던전에 대해 반복
        for (int i = 0; i < dungeons.length; i++) {
            int required = dungeons[i][0]; // 최소 필요 피로도
            int cost = dungeons[i][1]; // 소모 피로도

            // 아직 방문하지 않았고, 현재 피로도로 해당 던전을 탐험할 수 있다면
            if (!visited[i] && k >= required) {
                visited[i] = true;  // 방문 처리

                // 다음 던전 탐험 시도 (남은 피로도 감소, 탐험 수 증가)
                int result = dfs(k - cost, dungeons, visited, count + 1);
                
                // 지금까지 구한 최대 탐험 수와 비교하여 더 큰 값 저장
                maxCount = Math.max(maxCount, result);
                visited[i] = false;  // 백트래킹을 위한 방문 상태 복구
            }
        }

        return maxCount;  // 이 경로에서 가능한 최대 던전 수 반환
    }
}

다른 사람의 코드

class Solution {
    int dfs(int k, int[][] dungeons) {
        int cnt = 0;
        for(int[] d : dungeons) {
            int a = d[0], b = d[1];
            if(a <= k) {
                d[0] = 9999;
                cnt = Math.max(1 + dfs(k - b, dungeons), cnt);
                d[0] = a;
            }
        }
        return cnt;
    }
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        return dfs(k, dungeons);
    }
}

• boolean[] visit 대신 던전 최소 피로도 요구치를 올리는 방식