[프로그래머스] 피로도(Java), DFS

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

---

문제 풀이

완전탐색을 통해 탐색할 수 있는 모든 던전의 조합을 확인한다.

DFS를 수행하며 탐험한 던전의 최대값을 기록한다.

import java.util.*;

class Solution {
    static int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        
        DFS(visited, dungeons, k, 0);
        
        return answer;
    }
    
    private void DFS(boolean visited[], int[][] dungeons, int k, int count) {
        
        answer = Math.max(answer, count);
        
        for(int i=0; i<dungeons.length; i++) {
            if(k >= dungeons[i][0] && !visited[i]) {
                // 최소 피로도보다 현재 피로도가 높다면 체력 소모 O
                visited[i] = true;
                DFS(visited, dungeons, k - dungeons[i][1], count + 1);
                visited[i] = false;
            } 
        }
    }
}