프로그래머스 | LV.2 피로도 - 완전 탐색 (Java)

⬛ 프로그래머스 | LV.2 피로도 - 완전 탐색 

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

프로그래머스

문제 설명

---

💚문제 접근 방식

   1) 최소 피로도 : 해당 던전 탐험 (전) 필요한 최소 피로도

    2) 소모 피로도 : 해당 던전 탐험 (후) 소모되는 소모 피로도

    3) 하루에 한 번씩만 탐험 가능한 던전이므로 → (중복 방문 X) 방문체크

    4) 우리가 구해야 하는 것은 현재 k의 피로도로 탐험 가능한 최대 던전 수 (즉, 최대 깊이)

입출력 예시 설명

입출력 예시의 설명을 통해서 방문 순서도 중요한 것을 알 수 있다.

예를 들어 80 → 30 → 50 순으로 던전을 방문하면 최대 3개의 던전 탐험이 가능하지만

80 → 50 → 30 순으로 방문을 시도하면 갱신된 k가 마지막 던전 방문할 최소 피로도를 만족하지 못해서 최대 깊이 2까지만 탐험이 가능하다.

결국 완전 탐색으로 모든 탐험 경우의 수를 빠짐없이 체크하며 최대 깊이를 탐색해야 하는 ‘완전 탐색’ 문제인 것을 알 수 있다.

---

💚문제 풀이 방식

• DFS 로 모든 탐험 가능한 경우의 수를 빠짐없이 체크하며 풀었다. (완전 탐색)
• 매번 DFS로 다음 깊이에 방문했을 때 확인해야 하는 것은 1) 방문 여부 2) k≥최소 피로도 이다.

1) 해당 i번째 던전이 방문 전 상태인지
2) 현재의 k값이 해당 i번째 던전의 최소 피로도보다 큰지 

if(!visited[i] && k >= dungeons[i][0] ) //이 조건 만족해야 해당 깊이로 더 깊이 탐색 가능하기 때문

• 조건이 만족하면 visited로 방문 체크 후 k값은 소모 피로도 빼서 갱신시켜주고 다음 깊이에 대한 DFS를 호출하며 더 깊이 탐색을 시도한다.
• 이 과정에서 max값은 최대 깊이를 갖는 (방문 가능 던전 최대 개수) lv 값으로 계속 갱신해주고, 모든 호출이 반환된 시점에서 max를 answer에 넘겨주면 그게 정답이 된다 .

---

• 최근에 풀었던 문제를 다시 풀게 됐다. 더 상세한 풀이는 여기로

프로그래머스 | LV.2 피로도 - 완전 탐색, DFS 문풀

 

---

💚 제출 코드

import java.util.*;

class Solution {
    static boolean[] visited;//방문 1일 1회니까
    static int max = Integer.MIN_VALUE;//최소값 초기화
    //DFS
    static void DFS(int lv, int k, int[][] dungeons){
        
        for(int i=0; i<dungeons.length; i++){
            if(!visited[i] && k >= dungeons[i][0]){//방문안했고, 해당 던전 최소 피로도보다 k가 클 경우만 
                visited[i] = true;
                DFS(lv+1, k-dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        
        max = Math.max(max, lv);
    } 
    
    //솔루션
    public int solution(int k, int[][] dungeons) {
        int answer = 0;
        visited =new boolean[dungeons.length];//던전 방문 체크용
        
        DFS(0, k, dungeons);
        answer = max;//최대깊이 값 
        
        return answer;
    }
}