[Algorithm] Programmers_피로도 in Java

💡 Programmers Level 2. 피로도:

던전별 필요 피로도와 소모 피로도를 확인하여 가장 많은 던전을 탐색하는 경우의 수 찾기

🌱 코드 in Java

알고리즘: DFS

class Solution {
    int[][] copy;
    int len;
    int max = 0;
    boolean[] visit;
    public int solution(int k, int[][] dungeons) {
        copy = dungeons;
        len = copy.length;
        visit = new boolean[len];
        dfs(k, 0, 0);
        return max;
    }
    
    public void dfs(int k, int cnt, int d) {
        max = cnt > max ? cnt : max;
        if (d == len || max == len) // dfs 종료
            return ;
        for (int i = 0; i < len; i++) {
            if (!visit[i] && k >= copy[i][0]) { // 불필요한 탐색을 하지 않도록
                visit[i] = true;
                dfs(k - copy[i][1], cnt + 1, d + 1); 
                visit[i] = false;
            }
        }
    }
}

왜! 왜 이렇게 어려워!
순열을 통해서 완전 탐색을 해야하는 문제였다.
순열을 만들기 위한 DFS 고고.

현재 피로도보다 탐색하려는 던전의 최소 필요 피로도가 작을 경우에만
탐색할 수 있도록 함.

🧠 기억하자

1. 순열 알고리즘

• dfs로 탐색할 수 있다!