[프로그래머스] 피로도

코드 힌트

문제 이해:

• 주어진 k는 초기 체력이며, dungeons는 각 던전의 요구 체력과 체력 소모를 나타내는 2D 배열입니다.
• 목표는 체력을 최대한 소모하지 않고 가능한 많은 던전을 탐험하는 것입니다. 각 던전은 체력 요구와 소모량을 가지고 있습니다.

알고리즘 개요:

• DFS(깊이 우선 탐색)를 사용하여 모든 가능한 던전 탐험 조합을 탐색합니다.
• 각 던전의 탐험 가능 여부를 체크하고, 탐험 후 체력을 갱신하며 재귀적으로 탐색을 진행합니다.
• 최종적으로 탐험할 수 있는 던전의 최대 수를 반환합니다.

세부 단계:

1. DFS 탐색 초기화: dfs 함수를 호출하여 모든 가능한 탐험 조합을 시작합니다. 초기 체력과 던전 방문 여부를 초기화합니다.
2. 현재 탐험 상태 기록: 현재 탐험 가능한 던전의 수를 기록합니다. 이 값을 최대값으로 갱신합니다.
3. 탐험 가능한 던전 탐색: 현재 체력으로 탐험 가능한 던전을 탐색합니다. 던전의 요구 체력이 현재 체력 이하일 때만 탐험할 수 있습니다.
4. 재귀적 탐색: 탐험한 던전을 방문 처리하고, 체력을 소모한 후, 다음 던전 탐험을 위해 재귀적으로 dfs를 호출합니다.
5. 방문 처리 해제: 탐험 후에는 던전을 다시 방문하지 않도록 방문 처리를 해제합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    // 최대 탐험 던전 수를 저장할 전역 변수
    static int result = 0;
    
    public int solution(int k, int[][] dungeons) {
        // 던전 방문 여부를 기록할 배열 초기화
        boolean[] visited = new boolean[dungeons.length];
        // DFS 탐색 시작
        dfs(dungeons, visited, 0, k);
        // 최대 탐험 가능한 던전 수 반환
        return result;
    }
    
    public static void dfs(int[][] dungeons, boolean[] visited, int count, int k) {
        // 현재 탐험 가능한 던전 수를 최대값으로 갱신
        result = Math.max(result, count);

        // 모든 던전에 대해 탐험 가능 여부 확인
        for (int i = 0; i < dungeons.length; i++) {
            // 던전을 방문하지 않았고 현재 체력으로 탐험 가능한 경우
            if (!visited[i] && dungeons[i][0] <= k) {
                // 던전 방문 처리
                visited[i] = true;
                // 체력 소모 후 재귀적으로 탐색
                dfs(dungeons, visited, count + 1, k - dungeons[i][1]);
                // 던전 방문 처리 해제
                visited[i] = false;
            }
        }
    }
}