[Programmers / Level 2] 87946. 피로도 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/피로도

입출력 조건

입출력 예시

문제 이해

• 던전을 최대한 많이 탐험할 수 있는 경우를 찾는 문제

알고리즘

풀이 시간 : 28분

• 최대 방문 던전 수 갱신
• DFS
  • 현재 남은 피로도로 탐험 가능한 던전을 찾음
  • 방문 체크 후 해당 던전 탐험 (재귀 호출)
  • 탐험 후 방문 초기화 (DFS)

class Solution {
    int answer = 0;
    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) {
        answer = Math.max(answer, depth);

        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && k >= dungeons[i][0]) {
                visited[i] = true;
                dfs(depth + 1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
    }
}

결과