[프로그래머스] Lv.2 : 피로도 - 자바[Java]

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

프로그래머스

풀이 - 순열(DFS)

던전을 탐험할 수 있는 모든 경우를 구하고, 탐험한 던전 수를 구한다. 탐험한 던전 수가 모든 던전의 개수와 같다면 더 이상 탐색하지 않는다.

던전을 탐험할 수 있는 모든 경우는 순열(DFS)을 사용하여 구했다.

코드

class Solution {
    static int size;
    static int[] pm;
    static boolean[] check;
    static boolean flag;
    static int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        size = dungeons.length;
        pm = new int[size];
        check = new boolean[size];
        
        permutation(0, k, dungeons);
        
        return answer;
    }
    
    public static void permutation(int L, int k, int[][] dungeons) {
        if (flag) return; // 최댓값이 나왔으므로 더 이상 탐색할 필요가 없다
        
        if (L == size) {
            int cnt = count(k, dungeons);
            answer = Math.max(answer, cnt);
            
            if (answer == size) { // 최댓값이 나왔으므로 flag를 true로 업데이트
                flag = true;
            }
            return;
        }
        
        for (int i = 0; i < size; i++) {
            if (!check[i]) {
                pm[L] = i;
                check[i] = true;
                permutation(L+1, k, dungeons);
                check[i] = false;
            }
        }
    }
    
    public static int count(int k, int[][] dungeons) {
        int user = k;
        int cnt = 0;
        for (int idx : pm) {
            if (user >= dungeons[idx][0]) {
                user -= dungeons[idx][1];
                cnt++;
            }
        }
        
        return cnt;
    }
}

다른 풀이 - DFS(순열 X)

위의 풀이는 순열을 사용하여 던전의 순서를 저장했지만, 따로 저장할 필요 없이 DFS를 사용해도 모든 경우의 수를 구할 수 있다.

class Solution {
    static int size;
    static boolean[] visited;
    static boolean flag;
    static int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        size = dungeons.length;
        visited = new boolean[size];
        
        dfs(0, k, dungeons);
        
        return answer;
    }
    
    public static void dfs(int len, int k, int[][] dungeons) {
        if (flag) return; // 최댓값이 나왔으므로 더 이상 탐색할 필요가 없다
        
        for (int i = 0; i < size; i++) {
            if (!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true;
                dfs(len+1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        
        answer = Math.max(answer, len);
        
        if (answer == size) { // 최댓값이 나왔으므로 flag를 true로 업데이트
            flag = true;
        }
    }

}