[프로그래머스] Lv2. 피로도 (자바)

DFS / 완전 탐색

import java.util.List;

class Solution {

    public int answer;
    public boolean[] isVisit;

    public int solution(int k, int[][] dungeons) {
        int count = 0; // 던전 방문 횟수
        isVisit = new boolean[dungeons.length];  // 던전 방문 여부

        // 모든 던전 탐험
        explore(count, k, dungeons);
        return answer;
    }

    public void explore(int count, int k, int[][] dungeons) {
        // 던전 수 만큼 반복(탈출 조건)
        for(int i=0; i < dungeons.length; i++) {
            //(수행 동작)
            // 방문하지 않았고 최소 소모량이 현재 피로도보다 낮거나 같으면 방문
            if(!isVisit[i] && dungeons[i][0] <= k) {
                isVisit[i] = true;
                // 다음 던전 탐험
                explore(count+1, k-dungeons[i][1], dungeons);
                isVisit[i] = false; // 다음 회차에 영향 받지 않도록 재귀 함수 안에서 방문했던 내역 초기화
            }
        }
        answer = Math.max(answer, count);
    }

}