[JAVA] Lv.2 피로도 - 프로그래머스

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

프로그래머스

---

class Solution {
    static int dgNum, answer;
    static boolean[] visited;
    public int solution(int k, int[][] dungeons) {
        answer = 0;
        dgNum = dungeons.length;
        visited = new boolean[dgNum];
        explore(k, 0, dungeons);
        return answer;
    }

    private void explore(int now, int visitCnt, int[][] dungeons) {
        for (int i = 0; i < dgNum; i++) {
            if(!visited[i] && dungeons[i][0] <= now){
                visited[i] = true;
                explore(now - dungeons[i][1], visitCnt + 1, dungeons);
                visited[i] = false;
            }
        }
        //가능한 모든 던전에 대한 탐색을 마친 경우, 최댓값 갱신
        answer = Math.max(answer, visitCnt);
    }
}

• 던전을 방문하는 순서는 바뀔 수 있으므로 visited 배열로 방문 여부를 체크해 탐색한다
• '최소 필요 피로도 >= 소모 피로도' 가 항상 성립하므로, 탈출 조건으로 현재 피로도 < 0 인 경우를 줄 수 없다 (애초에 if조건에서 막히므로)
• 순서가 어찌된다고 해도, for문 탈출 == 모든 던전에 대한 탐색 한번씩 마침을 의미하므로 for문이 끝나고 answer을 갱신해준다.
  • 별도로 탈출 조건을 설정할 필요 없이 for안 if문에서 걸러짐을 활용