[programmers] 피로도 - Java

피로도

문제 설명

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.

• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
• dungeons의 가로(열) 길이는 2 입니다.
• dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
• "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
• "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
• 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

입출력 예 설명

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.

• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.

• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

solution.java

import java.util.*;
class Solution {
    public int answer;
    public boolean[] visited;

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(0, k, dungeons);
        return answer;
    }
    
    public void dfs(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true;
                dfs(depth + 1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth);
    }
}

핵심 키워드

• 최대 탐색 수를 담을 변수와 각 던전을 현재 탐색한 상태인지 나타내는 배열을 선언한다.

• 현재 깊이와 현재 피로도를 파라미터로 dfs 메서드를 실행한다.
• 첫 번째 던전부터 방문하며 만약 해당 던전을 탐색한 상태가 아니고, 현재 피로도가 방문한 던전의 필요 피로도보다 같거나 작은 경우, 다음과 같이 진행된다.
• 던전을 탐색한 것으로 표시하고, 깊이를 업데이트하고, 던전에서 소모한 피로도만큼 남은 피로도를 감소시키고, dfs를 재귀적으로 호출해서 추가적인 분기를 탐색한다.
• 해당 분기의 탐색이 끝나면 탐색했던 던전을 탐색하지 않은 던전으로 바꾼다.
• 현재 깊이와 최대 탐색 수를 비교해서 더 큰 값을 최대 탐색 수로 저장한다.

결론!