[Programmers] 피로도 JAVA

반응형

728x90

[Programmers] 피로도 - LV 2 

---

접근

• 완전 탐색

---

풀이

피로도가 주어지고 던전을 돌 때마다 던전이 요구하는 피로도가 소모된다. 던전에 입장하기 위한 최소 피로도가 존재할 때 가장 많은 던전을 탐험할 때 몇 개의 던전 탐험이 가능한지 구하는 문제이다. 그리디나 dp도 생각은 해봤는데 최소 피로도가 존재해 이전 선택이 다음 선택에 영향을 미치다 보니 그냥 완전탐색으로 풀었다. 

    private static int answer;
    
    public int solution(int k, int[][] dungeons) {
        answer = 0;
        boolean[] isVisited = new boolean[dungeons.length];
        dfs(k, dungeons, 0, isVisited);
        return answer;
    }

dfs를 이용해 모든 경로를 탐색해 주었다. 

    private void dfs(int k, int[][] dungeons, int count, boolean[] isVisited) {
        answer = Math.max(answer, count);
        for (int i = 0; i < dungeons.length; i++) {
            int need = dungeons[i][0];
            int use = dungeons[i][1];

            if (k < need || isVisited[i]) {
                continue;
            }

            isVisited[i] = true;
            dfs(k-use, dungeons, count + 1, isVisited);
            isVisited[i] = false;
        }
    }

 answer 변수를 전역으로 선언해 가장 많은 던전을 돌 수 있는 경우를 체크하고 현재 피로도가 던전 피로도 요구치보다 낮다면 패스해 주었다.

---

전체 코드

class Solution {
    private static int answer;
    
    public int solution(int k, int[][] dungeons) {
        answer = 0;
        boolean[] isVisited = new boolean[dungeons.length];
        dfs(k, dungeons, 0, isVisited);
        return answer;
    }
    
    private void dfs(int k, int[][] dungeons, int count, boolean[] isVisited) {
        answer = Math.max(answer, count);
        for (int i = 0; i < dungeons.length; i++) {
            int need = dungeons[i][0];
            int use = dungeons[i][1];

            if (k < need || isVisited[i]) {
                continue;
            }

            isVisited[i] = true;
            dfs(k-use, dungeons, count + 1, isVisited);
            isVisited[i] = false;
        }
    }
}