[PGS] 피로도 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

class Solution {
    
    static boolean[] used;
    static int answer = Integer.MIN_VALUE;
    
    public int solution(int k, int[][] dungeons) {
        used = new boolean[dungeons.length];
        dfs(k, 0, dungeons.length, 0, dungeons);
        return answer;
    }
    
    private void dfs(int k, int depth, int n, int cnt, int[][] dungeons) {
        answer = Math.max(answer, cnt);
        
        for (int i = 0; i < n; i++) {
            if (used[i] || k < dungeons[i][0]) {
                continue;
            }
            
            used[i] = true;
            dfs(k - dungeons[i][1], depth + 1, n, cnt + 1, dungeons);
            used[i] = false;
        }
    }
}

📄 해설

접근

• 재귀(DFS)를 사용하는 문제. 완전탐색은 일단 재귀로 먼저 접근해보면 대부분 재귀다.
• 모든 던전을 출발지로 지정하여 시작하도록, 반복문 내에서 재귀함수를 호출하면된다.
• 진행하면서 방문처리도 해주고, 최댓값 갱신도 해준다면 손쉽게 해결이 가능

과정

• 방문처리용 배열 used 는 던전의 개수만큼의 크기를 가지도록 초기화
• 재귀함수를 호출하여 프로세스를 시작한다. (dfs 호출)
• 각 던전 도착 시 마다 최대 방문 횟수인 answer 의 값을 갱신해준다.
• 반복문 내에서 다음 던전을 정하는 기준은 아래와 같다.
  1. 이전 경로에서 방문하지 않은 던전
  2. 최소 필요 피로도가 현재 피로도 보다 낮은 던전
• 위 기준에 따라 조건문으로 분기를 해주고, 다음 던전은 방문처리 해준다.
• 다음 던전에 대한 처리가 끝났다면 해당 던전의 방문처리를 해제한다.