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

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

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

프로그래머스

문제 설명

---

💚나의 풀이

• 문제에서 추론할 수 있는 핵심적인 사실은 다음과 같다.

목표 : 유저 탐험 가능한 최대 던전 수 구하기

각 던전은 하루에 한 번씩 탐험할 수 있다. ( = 중복 방문X. visited로 방문 체크해야 한다)

현재의 피로도 k 와 비교했을 떄, k보다 ‘최소 피로도’가 작거나 같아야 해당 던전 탐험이 가능하다.

각 던전마다 (최소 피로도, 소모 피로도) 가 존재한다.

---

• 이 문제는 ‘완전 탐색’ 문제이다.
• DFS(lv, 현재k)를 계속해서 방문 체크 하며 깊이 탐색해야 하고, 최대깊이로 뻗어갈 수 있을 때까지 가다가 더 이상 방문할 던전이 없는 상태에서 복귀하는데 그때의 최대 깊이 = 방문 가능한 최대 던전 수 가 되는 문제였다.
• 특히, 방문 순서도 중요하게 작용이 된다.
• 문제의 예시에서 현재 k= 80인데, 3개의 던전 중 80→30→50 순으로 간다면 3곳을 모두 방문이 가능하다.
• 그런데 현재 k=80인 상태에서, 80 → 50 으로 가버리면, 남은 피로도가 20이 되면서 더 이상 진입 가능한 던전이 없는 상태로 2곳이 방문 가능하다.
• 결국 각각의 깊이에서 모두 가능한 최대로 뻗어가보면서,  각 뿌리 별 최대 max 깊이가 무엇인지 갱신해가며  ‘완전탐색’을 시도해야 했던 문제이다. 주의하자.

나의 풀이 설명 그림

💚 제출 코드

import java.util.*;

class Solution {
    static int answer;
    static boolean[] visited;
    //DFS
    static void DFS(int lv, int k, int[][] dungeons){
        
        for(int i=0; i<dungeons.length; i++){
            //방문X && 최소 피로도가 k보다 작거나 같은 곳으로는 더 깊이 탐색 가능
            if(!visited[i] && k >= dungeons[i][0]){
                visited[i] = true;
                //더 깊이 레벨탐색, k-소모피로도 보내면서 점차 깊이
                DFS(lv+1, k - dungeons[i][1], dungeons);
                visited[i] = false;//복귀 시 false주기 (다른 뿌리에서도 완탐 해야 함)
            }
        }
        
        answer = Math.max(answer, lv);
        
    }
    //솔루션
    public int solution(int k, int[][] dungeons) {
        
        visited = new boolean[dungeons.length];
        
        DFS(0, k, dungeons);
        
        return answer;
    }
}